LeetCode75-790-Domino

动规五部曲

1. dp数组以及下标含义
2. 递归公式
3. dp数组如何初始化
4. 遍历顺序
5. 打印dp数组

🧠 Summary of Thoughts

可以先考虑简单一些的情况: How many ways that we can cover a 2 * N board using one type of domino (1 * 2)?

每个i列的时候，都可以是前面i-1的后面加上一个竖条。或者是i-2的后面补充上一个2条横条。其实此时就转化成了fibonacci。

同理，这道题目可以化简为如下图：

这里有三个状态：

• dp[i][0]: 前 i 列整整齐齐、完全填满（第 i 列的上下两格都被盖住了），没有任何格子凸出到第 i+1 列
• dp[i][1]: 前 i-1 列已经填满，但第 i 列只有上面那格被填了,下面那格是空的（等着后面的瓷砖来填）
• dp[i][2]: 前 i-1 列已经填满，但第 i 列只有下面那格被填了，上面那格是空的

✅ Code（Java）

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