bhw0506   3년 전

DP[n] = DP[n-1] * 2 + DP[n-2] 이런 점화식이 나오는데

DP[n-1] 은 0 X | X 0 이런식으로 2가지 경우의수로 DP[n-1]*2

그런데 마지막 DP[n-2]는 어떤 경우의수를 추가해 준것인가요??

사자가 우리에 없을 경우의수 X X | X X 인가요??

zlzmsrhak   3년 전

1) X X -> DP[n-1]

2) X 0 | ? ?, 0 X | ? ? -> 2*DP[n-1] 

3) X 0 | X 0, 0 X | 0 X -> DP[n-1] - DP[n-2]

총 가짓수는 1) + 2) - 3) = 2*DP[n-1] + DP[n-2] 입니다.

3)은 위의 두 칸을 하나로 합친 뒤 배열하되, 첫 줄에 하나는 있게 하는 배열의 가짓수이기 때문에,

전체 DP[n-1]에서 하나를 제외한 DP[n-2]를 빼주면 됩니다.


점화식은 쉬워보여도 증명은 어려울 수 있고, 저같은 경우는 열의 상태가 3가지 뿐이기 때문에 DP를 N*3으로 구현했습니다.

댓글을 작성하려면 로그인해야 합니다.