C++刷LeetCode（1411. 给 N x 3 网格图涂色的方案数）【动态规划】

糖逗

题目描述：

你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

 

示例 1：

输入：n = 1
输出：12
解释：总共有 12 种可行的方法：

示例 2：

输入：n = 2
输出：54
示例 3：

输入：n = 3
输出：246
示例 4：

输入：n = 7
输出：106494
示例 5：

输入：n = 5000
输出：30228214
 

提示：

n == grid.length
grid[i].length == 3
1 <= n <= 5000

class Solution {
public:
    int numOfWays(int n) {
            int mode = 1e9+7;
        if (n == 1) return 12;
        vector<long> a{6};
        vector<long> b{6};
        for (int i = 1; i < n; i++) {
            a.push_back((a[i - 1] * 3 + b[i - 1] * 2) % mode);
            b.push_back((a[i - 1] * 2 + b[i - 1] * 2) % mode);
        }
        return (a.back() + b.back()) % mode;
    }
};

参考链接：https://leetcode-cn.com/problems ... -gui-hua-by-klaxxi/

小甲鱼的铁粉

永恒的蓝色梦想

和你使用同样的方法，但减少了内存占用，提高了效率：

class Solution {
public:
    int numOfWays(int n) {
        const static int mod = 1000000007;
        long temp, a = 6, b = 6;

        while (--n) {
            temp = a;
            a = (temp * 3 + (b << 1)) % mod;
            b = (temp + b << 1) % mod;
        }

        return (a + b) % mod;
    }
};

少开数组总是好事。

永恒的蓝色梦想

第一次发现……力扣的测试机上的 long 是 64 位的……

糖逗

永恒的蓝色梦想 发表于 2020-6-26 11:54
和你使用同样的方法，但减少了内存占用，提高了效率：少开数组总是好事。