白峻1904号01タイル

白峻1904号。

タイル

動的計画法で問題を解決するとき、私たちと同じように繰り返し選択するルールが一番考えられます.
現在使用可能なタイルは「1」と「00」の2種類.
これが私たちが同じように繰り返した選択です.
1と00を選択してタイルを作成します.
まず1つ目、2つ目の長さのタイルを見てみましょう.

길이가 1인 경우 : '1'
길이가 2인 경우 : '00', '11'

長さが3なら

길이가 3인 경우 : '100', '001', '111'

これをもう一度考えなさい.

長さi-2のタイルに長さ2の00を貼り付けます.

長さi-1のタイルに長さ1のタイルを貼り付ける.

の2つのケースは、長さがiに達することを示している.
これはi>=3を繰り返すルールです.
長さiのタイルの個数をdp[i]と呼ぶと、
dp[i]=dp[i-2]+dp[i-1].
私たちはまた問題を15746部分に分けることを求めます.
dp[i]=(dp[i-2]+dp[i-1])%15746.
ソースコードは以下の通りです.