我想找到 4 x N 区域（4 个单位宽度和 N 个单位高度，N ≥ 1）多米诺骨牌砖的可能不同组合的数量使用动态规划 .
多米诺骨牌的尺寸为 2x1，例如
==
对于水平和
|
|
对于垂直砖。
Now,
示例 4x1（两块多米诺骨牌叠在一起）
====
4x2 砖块配置示例（共 5 个）
1)
||||
||||
2）（转动右边两块砖）
||==
||==
3)
|==|
|==|
4)
====
====
5)
==||
==||
迄今为止已知的独特组合数量
4x1 : 1 possibility
4x2 : 5 possibilites
4x3 : 11 possibilites
4x4 : 36 possibilites
解决一个更普遍的问题。求平铺 4×N 网格的方法数，其中顶行中的某些位置可能被占据。将每个位置与 2 的幂相关联，最左边对应 1，第二个 2，第三个 4，最右边 8。让T(N,k)是 4×N 网格的平铺数量，其中位置对应于k最上面一排已经被占用了。k == 0表示没有占据位置，k == 6表示两个中间位置被占用 (6 = 2 + 4) 等等。
然后找到转换，当填充顶行的剩余部分时，下一行中的哪些模式可以通过多少种方式到达？
例如，如果中间两个位置被占据，则填充顶行剩余部分的唯一方法是在最左和最右位置垂直放置多米诺骨牌，从而导致
|xx|
| |
以及占据下一行中的两个最外侧位置的配置，对应于1+8 = 9, so T(N,6) = T(N-1,9)。而对于k == 9，我们从看起来的情况开始
| |
我们有两种可能性，
|==| ||||
||
我们可以通过水平放置一个多米诺骨牌来填补间隙，让下一行完全自由，或者垂直放置两个多米诺骨牌，占据下一行的两个中间位置，所以
T(N,9) = T(N-1,0) + T(N-1,6)
使用这些转换来构建一个表T(n,k).
你想要找到的值是T(N,0).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
