백준 1010. 다리 놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

d[i][j] : 서쪽의 i개의 사이트, 동쪽의 j개의 사이트일때 다리를 놓을수 있는 경우의 수 

 

d[1][1] = 1 

d[1][2] = 2

d[1][3] = 3

d[1][4] = 4

 

d[2][1]은 동쪽의 사이트의 수가 서쪽의 사이트의 수보다 크거나 같다고 했으므로 고려할필요 없다.

d[2][2] = 1 

d[2][3]은? 서쪽의 첫번째 사이트를 동쪽의 첫번째 사이트에 연결하면, 나머지는 서쪽에 1개, 동쪽에 2개가 남는다 즉 d[1][2]와 같다

또한 서쪽의 첫번째 사이트를 동쪽의 두번째 사이트에 연결하면, 서쪽에 1개 동쪽에 1개가 남는다 (다리는 교차될수 없으므로). 

 

즉 점화식은 d[i][j] = d[i-1][j-1] + d[i-1][j-2] + ... + d[i-1][1]