Hard

题目描述

你有一个大小为 n x 3 的网格，你想要用红、黄、绿三种颜色给网格的每个单元格涂色，同时要确保没有两个相邻的单元格有相同的颜色（即，共享垂直或水平边的单元格不能有相同的颜色）。

给定网格的行数 n，返回你可以给这个网格涂色的方案数。由于答案可能很大，答案必须对 10^9 + 7 取模。

示例 1：

输入: n = 1
输出: 12
解释: 有 12 种可能的方式给网格涂色。

示例 2：

输入: n = 5000
输出: 30228214

约束条件：

  • n == grid.length
  • 1 <= n <= 5000

提示：

  • 我们将使用动态规划方法。我们将尝试所有可能的配置。
  • 设 dp[idx][prev1col][prev2col][prev3col] 为从第 idx 行到第 n-1 行给网格涂色的方案数，同时考虑到前一行（第 idx - 1 行）的颜色为 prev1col、prev2col 和 prev3col。构建 dp 数组来获得答案。

解题思路

这是一个经典的动态规划问题。我们需要考虑每一行的涂色方案，并确保相邻行之间没有冲突。

思路分析：

  1. 状态定义：对于每一行，我们可以将其涂色方案分为两类：

    • ABA型：三个位置的颜色为 A-B-A 形式，如红-黄-红
    • ABC型：三个位置的颜色都不同，如红-黄-绿

  2. 状态转移：

    • 第一行：ABA型有 6 种方案（3种颜色选A，2种颜色选B），ABC型有 6 种方案（3×2×1）
    • 对于后续行，需要考虑与前一行的兼容性：
      • 当前行ABA型可以由前一行的3个ABA型和2个ABC型转移而来
      • 当前行ABC型可以由前一行的2个ABA型和2个ABC型转移而来

  3. 优化：我们不需要记录具体的颜色组合，只需要记录每种类型的方案数即可。

这种方法的关键在于识别出只有两种基本模式，大大简化了状态空间。

代码实现

class Solution {
public:
    int numOfWays(int n) {
        const int MOD = 1000000007;
        
        // ABA型：6种方案，ABC型：6种方案
        long long aba = 6, abc = 6;
        
        for (int i = 1; i < n; i++) {
            long long new_aba = (3 * aba + 2 * abc) % MOD;
            long long new_abc = (2 * aba + 2 * abc) % MOD;
            aba = new_aba;
            abc = new_abc;
        }
        
        return (aba + abc) % MOD;
    }
};

class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # ABA型：6种方案，ABC型：6种方案
        aba, abc = 6, 6
        
        for i in range(1, n):
            new_aba = (3 * aba + 2 * abc) % MOD
            new_abc = (2 * aba + 2 * abc) % MOD
            aba, abc = new_aba, new_abc
        
        return (aba + abc) % MOD

public class Solution {
    public int NumOfWays(int n) {
        const int MOD = 1000000007;
        
        // ABA型：6种方案，ABC型：6种方案
        long aba = 6, abc = 6;
        
        for (int i = 1; i < n; i++) {
            long newAba = (3 * aba + 2 * abc) % MOD;
            long newAbc = (2 * aba + 2 * abc) % MOD;
            aba = newAba;
            abc = newAbc;
        }
        
        return (int)((aba + abc) % MOD);
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
    const MOD = 1000000007;
    
    // ABA型：6种方案，ABC型：6种方案
    let aba = 6, abc = 6;
    
    for (let i = 1; i < n; i++) {
        let newAba = (3 * aba + 2 * abc) % MOD;
        let newAbc = (2 * aba + 2 * abc) % MOD;
        aba = newAba;
        abc = newAbc;
    }
    
    return (aba + abc) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历n行，每行的计算是O(1)
空间复杂度O(1)只使用常数个变量存储状态

相关题目