[python/伯準/DP]1333:タイル詰め

じゅうてんタイル

質問する

入力

しゅつりょく

例

に答える

Nが奇数のときはいつもタイルが欠けています!=>偶数でしか考えられません.

N=2はを表す

N=4はを表す

   1번 + 1번, 	1번 + 2번, 	1번 + 3번 
    2번 + 1번, 	2번 + 2번, 	2번 + 3번 
    3번 + 1번, 	3번 + 2번, 	3번 + 3번 

3-2)2つ目のケースを考える
3-2)の3-1)回のように,3 x 2の場合は3 x 4の場合に乗じて,중복が発生するのは当然である.3 x 4は3 x 2を含むからです.下の写真を見ると分かりやすいはずです.
したがって,3 x 2タイルと3 x 4タイルが重ならない場合を考慮すべきである.
まだ数えられていない場合、数は3 x 2タイルと2個の3 x 4固有タイルの場合です.
私たちは3-1番ボックスで固有の3 x 4タイルに3 x 2タイルを貼った場合を数えました.
そのため、3 x 2タイルに固有の3 x 4タイルを貼ることだけを考えれば、3 x 4と3 x 2タイルを繰り返さずに数えることができます!番目の数字は、3 x 2のタイルに2つの3 x 4の唯一のタイルが付着している.dp[2]*2.

3-3)N=6で唯一?あと2つ作ろう

てんかしき

正しいコード

n = int(input())

dp = [0]*(n+1)

dp[0] = 1

if n  >= 2:
    dp[2] = 3

for i in range(4,n+1,2):
    dp[i] = dp[i-2] *dp[2]
    for j in range(0,i-2, 2):
        dp[i] += dp[j]*2

print(dp[n])

感じる？

ランタイムエラー
nが2より大きい場合は考えられなかったので、運転時に現れました...
白俊は難しいから...思いがけない例がたくさんありますㅠ!
修正前dp[0]=1,dp[2]=3
このように値を割り当てると、N=1の場合、上のコードにインデックスエラーが発生します.
(dp[2]は存在しません!)
他の人はdp=[0]*31(問題で与えられたnの最大値)という方法で解くので、この方法も考えてみましょう.