🎨 初学者友好指南《Number of Ways to Paint N 3 Grid》 – LeetCode 1411 (C++, Python, JavaScript)

Source: Dev.to

问题概述

已知条件：

• 一个大小为 n 行 3 列的网格。
• 三种可用颜色：红色、黄色和绿色。
• 相邻单元格（水平或垂直）不能使用相同颜色的规则。

目标

• 计算整个网格的涂色方案总数。
• 返回结果对 (10^9+7) 取模。

思路

由于每行只有三个格子，所有合法的行只能属于以下两种模式：

在从第 i 行移动到第 i + 1 行时，需要统计在不违反相邻规则的前提下，能够在已有行下面放置的每种类型的新行数：

• 在 ABA 行下面：可以放置 3 种 ABA 行和 2 种 ABC 行。
• 在 ABC 行下面：可以放置 2 种 ABA 行和 2 种 ABC 行。

只保留 ABA 行和 ABC 行的计数，并在每增加一行时更新它们，即可得到线性时间的解法。

代码块

C++

class Solution {
public:
    int numOfWays(int n) {
        constexpr int kMod = 1000000007;
        long color2 = 6; // ABA patterns
        long color3 = 6; // ABC patterns

        for (int i = 1; i < n; ++i) {
            long next_color2 = (color2 * 3 + color3 * 2) % kMod;
            long next_color3 = (color2 * 2 + color3 * 2) % kMod;
            color2 = next_color2;
            color3 = next_color3;
        }
        return (color2 + color3) % kMod;
    }
};

Python

k_mod = 10**9 + 7
# color2 = ABA patterns, color3 = ABC patterns
color2 = 6
color3 = 6

for _ in range(1, n):
    next_color2 = (color2 * 3 + color3 * 2) % k_mod
    next_color3 = (color2 * 2 + color3 * 2) % k_mod
    color2, color3 = next_color2, next_color3

result = (color2 + color3) % k_mod

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var numOfWays = function(n) {
    const kMod = 1000000007n; // BigInt for safety
    let color2 = 6n; // ABA
    let color3 = 6n; // ABC

    for (let i = 1; i < n; i++) {
        const nextColor2 = (color2 * 3n + color3 * 2n) % kMod;
        const nextColor3 = (color2 * 2n + color3 * 2n) % kMod;
        color2 = nextColor2;
        color3 = nextColor3;
    }

    return Number((color2 + color3) % kMod);
};

关键要点

• 状态压缩： 将行配置归类为 ABA 与 ABC 两种模式，避免逐一跟踪每一种颜色组合。
• 线性时间复杂度： 算法在 O(n) 时间内完成，只遍历一次所有行。
• 模运算： 在每一步都取模，防止计数指数增长导致溢出。

结束语

此题是状态转移动态规划的绝佳入门案例。类似的模式计数技巧在实际场景中也很常见，如资源调度和地图着色算法——相邻实体必须不同。掌握这些计数问题是通过顶尖公司技术面试的重要一步。