Daily LeetCode – day0106 0790. Domino and Tromino Tiling

// 0790. Domino and Tromino Tiling
class Solution {
    public int numTilings(int n) {
        if (n < 3) return n;
        final long MOD = 1000000007;
        long[] fullTiling = new long[n + 1];
        long[] partTiling = new long[n + 1];
        fullTiling[1] = 1;
        fullTiling[2] = 2;
        partTiling[1] = 0;
        partTiling[2] = 1;
        for (int i = 3; i <= n; ++i) {
            fullTiling[i] = (fullTiling[i - 1] + fullTiling[i - 2] + partTiling[i - 1] + partTiling[i - 1]) % MOD;
            partTiling[i] = (partTiling[i - 1] + fullTiling[i - 2]) % MOD;
        }
        return (int) fullTiling[n];
    }
}
学习笔记:
这是一道动态规划的题目,要仔细分析出四种不同的情况。
空的,上面凸出来的,下面凸出来的,满的。
也可以分为两种,部分完成和全部完成。
这两种思路都可以完成这道题目。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注