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

如果是2d，递推公式不难想出来。但是换成3d了，脑子有点转不过来了，可以给点思路吗

令f(n)表示2x2xn的组合数（最顶层无缺口），g(n)表示高度为n的顶上有2/4突出的组合数（即取走一个横着的积木），h(n)表示高度为n的顶上有3/4突出的组合数（即取走一个竖着的积木）。

1. f(n) = 2*g(n) + h(n)
   
2. g(n) = f(n-1)+ g(n-1)
   
3. h(n) = f(n-2) + 2*g(n-1)

复制代码

可以把h(n)消掉得到

1. f(n) = 2*g(n) + 2* g(n-1) + f(n-2)
   
2. g(n) = g(n-1) + f(n-1)

复制代码

base case:

• f(0) = 1, for convenience, 没有积木时算1种valid组合
• g(0) = 0，for convenience
• g(1) = 1
• f(1) = 2
  

sample results when n is small：
f(2) = 9, g(2) = 3
f(3) = 32, g(3) = 12
f(4) = 121, g(4) = 44

从2*2底部向上搭建n层，只可能出现两种状态，一是最下层是平的，二是有一半连着的凸出（只可能上下左右四种情况，且这一半是两块竖着放导致的）。用0，1分别表示上述两种状态。不会出现第三种情况是因为1个突出、2个对角突出、3个突出是配不平的。
设dp[n][state]表示已经有n层完整且状态是state时的方法数，求dp[n][0]

递推公式:
对 n >= 2有
dp[n][0] = 2 * dp[n - 1][0] + dp[n - 1][1] + dp[n - 2][0]
dp[n][1] = 4 * dp[n - 1][0] + dp[n - 1][1]
edge case:
dp[0][0] = 1, dp[0][1] = 1
dp[1][0] = 2, dp[1][1] = 4

则dp[2][0] = 9, dp[3][0] = 28

参考790题写的，lz可以试试看对不对

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

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

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];
        }
}

可以给下n=2的结果不？是9种嘛？

考虑了cube竖起来了没

我来帮楼主补剩下的图吧，我也正在寻找解法：

会不会和catalan number有关？

求一个链接~ 或者n <= 5的base case

是不是tiktok哈哈

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

你好，请问换成java代码应该怎么写呢，这个公式有点看不懂呢，谢谢