LeetCode - 1411. Number of Ways to Paint N × 3 Grid

Hard

1411. Number of Ways to Paint N × 3 Grid

題目

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colors: Red, Yellow, or Green while making sure that no two adjacent cells have the same color (i.e., no two cells that share vertical or horizontal sides have the same color).

Given n the number of rows of the grid, return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo .

Example 1

Input: n = 1
Output: 12
Explanation: There are 12 possible ways to paint the grid.

Example 2

Input: n = 5000
Output: 30228214

Constraints

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

解題思路

經典狀態 DP 題
三色塗格，相鄰（上下左右）不可相同

• 第 1 列有兩種起始可能：

  • ABC 類型（三個顏色都不同）
    R G Y
    Y R G
    一列裡合法排列數量：3 × 2 = 6

  • ABA 類型（左右同色，中間一定不同）
    R G R
    Y R Y
    一列裡合法排列數量：3 × 2 = 6

• 下一列轉移關係如下：

  • 第 i 列是 ABC

    • 從前一列 ABC 轉來：2 種
      R G Y
      下一列可轉：Y R G 或 G Y R
    • 從前一列 ABA 轉來：2 種
      R G R
      下一列可轉：Y R G 或 G R Y
    • 因此：dpA[i] = dpA[i-1] * 2 + dpB[i-1] * 2

  • 第 i 列是 ABA

    • 從前一列 ABC 轉來：2 種
      R G Y
      下一列可轉：G Y G 或 G R G
    • 從前一列 ABA 轉來：3 種
      R G R
      下一列可轉：Y R Y 或 G R G 或 G Y G
    • 因此：dpB[i] = dpA[i-1] * 2 + dpB[i-1] * 3

• 最後答案為：
  dpA + dpB

Solution Code

Time Complexity
O(n)

Space Complexity
O(1)

class Solution {
public:
    int numOfWays(int n) {
        const int MOD = 1e9 + 7;

        // 第 1 列有兩種起始可能
        long long dpA = 6; // ABC 類型
        long long dpB = 6; // ABA 類型

        for (int i = 2; i <= n; i++) {
            long long nextdpA = (dpA * 2 + dpB * 2) % MOD;
            long long nextdpB = (dpA * 2 + dpB * 3) % MOD;

            dpA = nextdpA;
            dpB = nextdpB;
        }
        return (dpA + dpB) % MOD;
    }
};