求助一道动态规划的题目：dominos Tiling 3d

public class Domino_3D {
        private int mod = 1000000007;
        public int numTilings(int n) {
                long[] dp = new long[n+2];
                long[] dpa = new long[n+2];
                dp[0] = 1;
                dp[1] = 2;
                dpa[0] = 0;
                dpa[1] = 1;
                for(int i =2;i<=n;i++) {
                        dpa[i] = dpa[i-1]+dp[i-1] % mod;
                        dp[i] = (2*dpa[i]+2*dpa[i-1]+dp[i-2]) % mod;       
                }
                return (int)dp[n];
        }
}

Harry·Sun 发表于 2022-1-8 14:23
public class Domino_3D {
        private int mod = 1000000007;
        public int numTilings(int n) {

好人一生平安

wangshibo1993 发表于 2022-1-6 00:22
令f(n)表示2x2xn的组合数（最顶层无缺口），g(n)表示高度为n的顶上有2/4突出的组合数（即取走一个横着的积 ...

怎么说呢，感觉内在逻辑还是有点弄不懂。能否麻烦讲稍微详细一点？我看这道题google也没有答案

这道题的正确打开方式是想象力的问题。一定要把790. Domino and Tromino Tiling做了，看下solutions中关于“铺满”和“partial铺满”的概念，再来看这道题，就感觉茅舍顿开。

Harry·Sun 发表于 2022-1-8 12:23
public class Domino_3D {
        private int mod = 1000000007;
        public int numTilings(int n) {

  dpa[i] = dpa[i-1]+dp[i-1] % mod;
这个mod之前为什么不打括号 把之前加和啊？

我已全仓 发表于 2022-1-4 13:18
从2*2底部向上搭建n层，只可能出现两种状态，一是最下层是平的，二是有一半连着的凸出（只可能上下左右四种 ...

dp[n][0] = 2 * dp[n - 1][0] + dp[n - 1][1] + dp[n - 2][0]
==>dp[n][0] = 2 * dp[n - 1][0] + dp[n - 1][1] + dp[n - 2][0] * 5
最后一项是要*5吧，因为五种组合搭建2层完整色块？

解题思路利用动态规划，求解每一层的方案总数


前置约定
状态描述
为了方便表述每一层的状态，我们用0，1表示当前层4个格子的状态。
1.    0: 当前位置被填，并不向上伸出
2.    1: 当前位置被填，并向上伸出

note：因为每一层都是2*2， 我们会得到例如下面的状态（举例部分）：
0 0        1 1.           1 1  
1 1        0 0.           1 1
这样表达比较清晰，但是为了编辑方便以及后续dp的规整，这里转化为一行，分别为0011， 1100, 1111.

Example-1

底下红色层的状态表示0000，因为都没有向上伸出。灰色这一层同理也是0000.
Example-2

底下一层状态为1111，因为都伸到第二层。第二层状态为0000，因为并没有伸出。
Example-3

底下一层状态为1100，因为红色块伸到第二层，灰色没有。第二层状态为0000，因为并没有伸出。

摆放方向说明
以example3为例。看第一层（最下面的），如图


从4个方向看，会有四种变体
11
00

（俯视图）
1 0
1 0

（俯视图）
以及另外两个方向，这里统一按照 0011记录。但从数量上来说，是4种不同的摆放方案。这里我们称为0011 state家族

对于其他状态同理。

合法的状态家族

能够合法摆放的状态一共有以下三种state家族
state1（0000）， state2（0011）， state3（1111）
其他状态均为非法，可以自行想象一下，是否存在0111， 0001. （0横着放不伸到下一层，1竖着放伸到下一层）。

DP解题
DP定义: dp[i][state], 第i层以state为状态的摆放方法总数。
DP边界条件：dp[0][state1] = 0, dp[0][state2] = 0, dp[0][state3] = 0.    dp[1][state1] = 2, dp[1][state2] = 4, dp[1][state3] = 1.
DP 转移：


state1 : 0000 这一层都不向下一层伸出。    当前层摆法：上一层基于0000有2种，基于0011有1种，基于1111有1种
state2 : 0011 这一层有两个向下一层伸出 当前层摆法：基于0000有 4种，基于0011有1种
state3 : 1111 这一层四个都向下一层伸出 当前层摆法* 1

dp[i][state1] = dp[i - 1][state1] * 2 + dp[i-1][state2]*1 + dp[i-1][state3]*1
dp[i][state2] = dp[i - 1][state1] * 4 + dp[i-1][state2]*1 （*1 due to cannot overlap, only one way based on dp[i-1][state2])
dp[i][state3] = dp[i-1][state1] * 1

DP 答案：
dp[N][state1]

因为state无法直接作为index，我们可以用0 代表 0000， 1代表0011， 2代表1111.

Code

1. public class ThreeD {
   
2.     public static long getResult(int n) {
   
3.          long[][] dp = new long[n + 1][3];
   
4.          dp[1][0] = 2;
   
5.          dp[1][1] = 4;
   
6.          dp[1][2] = 1;
   
7. 
   
8.      for(int i = 2; i <= n; i++){
   
9.           dp[i][0] = dp[i - 1][0] * 2 + dp[i-1][1] * 1 + dp[i-1][2] * 1;
   
10.           dp[i][1] = dp[i - 1][0] * 4 + dp[i-1][1] * 1;
    
11.          dp[i][2] = dp[i-1][0] * 1;
    
12.       }
    
13. 
    
14.      return dp[n][0];
    
15.     }
    
16. 
    
17.      public static void main(String[] args) {
    
18.            System.out.println(ThreeD.getResult(5));
    
19.        }
    
20. }

复制代码

第一次在地里回答。有错误请及时指出。

马保国骑马保国 发表于 2022-7-7 17:12
解题思路利用动态规划，求解每一层的方案总数

纠正一下：dp转移里面说的下一层是逻辑上的接下来的一层，在物理上是上面一层。类似的，转移说的上一层是逻辑上的已经处理过的之前的那一层，在物理上是下面一层。