[アルゴリズム/標準]1309:動物園(python)

二つの方法がある.
1.検索ルール
0 1 2 3 4
1 3 7 17 41
dp[i]=dp[i-1]*2+dp[i-2]
こんなルールがあります.

N = int(input())
dp = [1, 3] + [0] * N

for i in range(2, N+1):
    dp[i] = (dp[i-1] * 2 + dp[i-2]) % 9901
print(dp[N])

しかし、このように解決すれば、dp問題を解決することは難しい.
2.以前に使用
以前の状況を使用しなければなりません...現在選択可能な場合:
1.ライオンを入れない
2.左側に入れる
3.右側に置く
3種類あります.
ライオンを入れなければ、前の格子の中で可能な場合は1,2,3でも構いません.
ライオンを左に置くと入れません.右に置くと2つの可能性があります.
ライオンは右に置かないで、左に2種類置くことができます.
点火方式で
0=未挿入の場合、1=左、2=右
dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-2][2]
dp[i][1] = dp[i-1][0] + dp[i-1][2]
dp[i][2] = dp[i-1][0] + dp[i-1][2]

N = int(input())
dp = [[1, 1, 1] for _ in range(N+1)]
for i in range(2, N+1):
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901
    dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901
    dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % 9901
print(sum(dp[N]) % 9901)