0927アルゴリズム11726 xNタイル

質問:https://www.acmicpc.net/problem/11726
イニシャル構想プロセス

室はすでにSWEAでこの問題を解決した.

dp[i] = dp[i - 1] + dp[i - 2]

最終コード

import sys
input = sys.stdin.readline

num = int(input())
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for i in range(3, num + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
if dp[num] < 10007: print(dp[num])
else: print(dp[num] % 10007)

DPはなぜこうなったのか.

dp[i-2]では、横並びのタイルを2枚追加するだけです.
dp[i−1]の場合、起立したタイルを1枚貼ることを考慮すると、以下のすべての場合の数を算出することができる.
したがって,このようにDPを適用すれば,答えを見つけることができる.