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

6024 ワード
algorithm テキストリンク

じゅうてんタイル


質問する


3×Nサイズの壁2×1, 1×2サイズのタイルで埋めたときの数字.

入力


第1行はN(1≦N≦30)を与える.

しゅつりょく


1行目の出力状況の数.

例



に答える

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

  • N=2はを表す

  • N=4はを表す
  • N=2の場合
    タイルの数は3なので9タイルの数は
       1번 + 1번, 	1번 + 2번, 	1번 + 3번 
    2번 + 1번, 	2번 + 2번, 	2번 + 3번 
    3번 + 1번, 	3번 + 2번, 	3번 + 3번
    で、
  • N=4で一意(?)2つの形のタイルが存在する.
    したがって、dp[4]=dp[2]*dp[2]+2=11となる.
  • N=6は
    • を表す.

  • タイルの場合は数を分けて考えなければなりません.
    .
    3-1)(3×4)のタイル上(3×2)のタイル
    3-2)(3 x 2)のタイル(3 X 4)
    3-3)(3×6)2個のユニークなパターンのタイル
    .

  • 3−1)第3のケースは当然3 X 4のタイルに3 X 2が付着したタイルである.
    答えは3 x 4タイルの数に3 x 2タイルの数を乗じたものです.dp[6] = dp[4] * dp[2]です.
    .

  • 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つ作ろう

  • すべての状況の数字を組み合わせるdp[6] = dp[4]*dp[2] + dp[2]*2 + 2 = 41.
  • N=8
  • N=8の場合、同じ場合、タイルの数を分けて考えればよい.
    .
    4-1)(3×6)のタイル(3×2)
    4-2)(3 X 4)の中のタイル(3 X 4)(3 X 4の唯一のタイル2個)
    4-3)(3 x 2)のタイル(3 X 6)(2個の3 X 6唯一のタイル)
    .
    • したがって、dp[8]dp[8] = dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2 で表現できます.

    てんかしき


    上記のルールでは、次の点火式をエクスポートできます.
    dp[0]は1に指定します.(Nが4より大きい場合は、常に2つの唯一のタイルを考慮する)dp[N] = dp[N-2]*dp[2] + dp[N-2-2]*2 + dp[N-2-2-2]*2 ... dp[0]*2 (단, N은 4보다 크다)

    正しいコード

    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の最大値)という方法で解くので、この方法も考えてみましょう.
    • リファレンス
    https://yabmoons.tistory.com/536
    ストリームテキストの実装
    Gnuboard & PHP