No.663
上段 \(i\) 番目, \(i+1\) 番目の数字と下段 \(i+1\) 段目の数字から上段 \(i+1\) 番目, \(i+2\)番目のどの数字に遷移できるかが分かる.
上段 i, i+1 番目 | 下段 i+1 番目 | 上段 i+1, i+2 番目 |
---|---|---|
00 | 0 | 00 |
1 | 01 | |
11 | 0 | 11 |
1 | 10 | |
01 | 0 | - |
1 | 10,11 | |
10 | 0 | 00 |
1 | 01 |
まずは下段1番目の数字から上段の \(N\) 番目, 1番目, 2番目の数字を仮定する.
そして上記の表を使って DP で上段の \(i\) 番目, \(i+1\) 番目の数字ごとに遷移できる組み合わせの数を求める.
端まで計算したら, 最初の仮定と合っている数字の組み合わせ数を取得する.