1010번 다리 놓기

점화식으로 풀어도 되고 조합으로 풀어도 된다(단, 조합으로 풀 경우 크기가 크므로 조심해야된다).

 

F[3][4]를 구해보자(발그림 죄송합니다).

맨 위 두 점을 연결하면 F[2][3]을 구하면 된다.

 

 

 

 

 

 

 

그 다음 점을 연결하면 F[2][2]를 구하면 된다.

 

 

 

 

 

 

 

이 두 경우를 더하면 F[3][4]의 값이 나온다. 

F[3][4] -> F[2][]+F[2][3]

F[3][5] -> F[2][2]+F[2][3]+F[2][4]

F[3][6] -> F[2][2]+F[2][3]+F[2][4]+F[2][5]

 

즉, 점화식은 F[M][N] = F[M-1][N-1] + F[M-1][N-2] + F[M-1][N-3] +.........+F[M-1][M-1]

               (입력 M과 N을 문제와 반대로 입력해버려서 반대인 상태로 설명)

 

이 점화식에 따라 코드를 작성하면 된다.

 

cache[30][30]까지 값을 다 구해놓고 입력 받은 M,N에 따라 해당 cache[M][N]값만 출력해도 된다.