[BOJ]1726 xnタイル(DP)

📃 2 xnタイル

コード#コード#

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

dp = [0] * 1001
dp[1]= 1 
dp[2] = 2

for i in range(3,1001):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007


print(dp[n])

問題を解く

絵を描くのは簡単だ.

長さnの矩形の場合
前述したように、dp[n−1]およびdp[n−2]が存在する.
点火式はdp[n]=dp[n−1]+dp[n−2]である.