Leetcode每日一题：1411. 给 N x 3 网格图涂色的方案数

Leetcode每日一题 —— 1411. 给 N x 3 网格图涂色的方案数

今天我们讨论的是Leetcode上的一个困难问题：1411. 给 N x 3 网格图涂色的方案数。这个问题要求我们计算用不同颜色给 N x 3 的网格图涂色，使得相邻两行不能完全相同的不同涂色方案的数量。下面是详细的解题思路和代码实现。

思路：
每一行有12种排列方式，第一个用例已经给出了。根据题目描述，我们可以总结出以下递推关系：

1. 如果上一行是同色，下一行有3种同色，2种不同色结果
2. 如果上一个不是同色，下一行有2种同色，2种不同色结果
   利用递推或动态规划的方法，我们可以计算出最终的方案数。

代码实现：

public int numOfWays(int n) {
    final int MOD = 1000000007;
    // 如果上一行是同色，下一行有3种同色，2种不同色结果
    // 如果上一个不是同色，下一行有2种同色，2种不同色结果
    long same = 6, diff = 6;
    while (--n > 0) {
        long nextSame = (same * 3 + diff * 2) % MOD;
        long nextDiff = (same * 2 + diff * 2) % MOD;
        same = nextSame;
        diff = nextDiff;
    }
    return (int) ((same + diff) % MOD);
}

这个代码首先初始化了same和diff为6，分别代表上一行同色和不同色的情况。然后通过循环，根据递推关系更新same和diff的值，直到计算出最终的方案数。最后，返回结果时对MOD取模，确保结果在整数范围内。

总结：
这个问题通过递推关系和动态规划的方法可以有效地解决。关键在于理解相邻两行不能完全相同的条件，并据此设计递推公式。希望这个解答对您有所帮助！