[問題解決]標準-117272722*nタイル2(dp)

3582 ワード
ProblemSolving テキストリンク

提问链接


問題の説明


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

入力


最初の行はnです.(1 ≤ n ≤ 1,000)

しゅつりょく


1行目2×n矩形を充填する方法数を10007で割った後、残りを出力する.

入力例1


2

サンプル出力1


3

入力例2


8

サンプル出力2


171

入力例3


12

サンプル出力3


2731

私の答え


いくつかのdp問題を解くとき,一番後ろにルールを見つければ点火式を簡単に導出できることを感じた.
この問題も同様に背後で考えている.
横長がiのタイルの場合、i−1まで充填されていれば、2 x 1キャップを充填することができる.
i−2に充填されている場合、1つのx 2が2つ、1つのx 2が1つの蓋である.ここでは2 x 1トップカバーは考慮しません.上から考えたからです.
点火式で表すとdp[i] = dp[i-1] + dp[i-2]*2です

注意事項


簡単に解けますが、落とし穴があります.
コードにn=1と入力します.
dp[2]=3初期化部はコンパイルエラーを引き起こす.
n=1の場合は異常処理を行います.

コード#コード#

n = int(input())

dp = [0]*(n+1)

if n < 2:
    print(1)
    
else:
    dp[1] = 1
    dp[2] = 3
    for i in range(3, n+1):
        dp[i] = dp[i-1] + 2*dp[i-2]
    print(dp[n]%10007)
アルゴリズムシミュレーション試験
Algorithm | DFS/BFS