[python] 2×nタイル2

白駿11727号です。

問題の説明

2×n矩形は1×2, 2×第1課×2つのタイルで充填された数を求めるプログラムを作成してください.
下図2×17長方形の一例を塗りつぶします.

に答える

2×nタイル題と同じように、1つの条件しか追加されていません.
今回は2×2タイルで充填した場合の数を計算します.

2 x 1タイル

1 x 2タイルが2マスを占めています
上記条件において、

2 x 2タイルは2つの格子

を占めている.
この条件は付加されている.
やはり絵で表すと.

上記の条件の下で

これで2 x 2タイルが右側の場合の数が増えます.
この場合、残りの部分はn-2となる.
点火式は以下の通り.
dp[n] = dp[n-1] + dp[n-2]*2

コミットコード

import sys

n = int(sys.stdin.readline())

dp = [1] * (n + 1)
result = 0

if n == 1:
    result = 1
else:
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] * 2

    result = dp[n] % 10007

print(result)