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으로 구현했습니다.
bhw0506 7년 전 1
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 인가요??