Welcome to Subscribe On Youtube
1411. Number of Ways to Paint N × 3 Grid
Description
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 10^{9} + 7
.
Example 1:
Input: n = 1 Output: 12 Explanation: There are 12 possible way to paint the grid as shown.
Example 2:
Input: n = 5000 Output: 30228214
Constraints:
n == grid.length
1 <= n <= 5000
Solutions
Solution 1: Recursion
We classify all possible states for each row. According to the principle of symmetry, when a row only has $3$ elements, all legal states are classified as: $010$ type, $012$ type.
 When the state is $010$ type: The possible states for the next row are: $101$, $102$, $121$, $201$, $202$. These $5$ states can be summarized as $3$ $010$ types and $2$ $012$ types.
 When the state is $012$ type: The possible states for the next row are: $101$, $120$, $121$, $201$. These $4$ states can be summarized as $2$ $010$ types and $2$ $012$ types.
In summary, we can get: $newf0 = 3 \times f0 + 2 \times f1$, $newf1 = 2 \times f0 + 2 \times f1$.
The time complexity is $O(n)$, where $n$ is the number of rows in the grid. The space complexity is $O(1)$.
Solution 2: State Compression + Dynamic Programming
We notice that the grid only has $3$ columns, so there are at most $3^3=27$ different coloring schemes in a row.
Therefore, we define $f[i][j]$ to represent the number of schemes in the first $i$ rows, where the coloring state of the $i$th row is $j$. The state $f[i][j]$ is transferred from $f[i  1][k]$, where $k$ is the coloring state of the $i  1$th row, and $k$ and $j$ meet the requirement of different colors being adjacent. That is:
\[f[i][j] = \sum_{k \in \text{valid}(j)} f[i  1][k]\]where $\text{valid}(j)$ represents all legal predecessor states of state $j$.
The final answer is the sum of $f[n][j]$, where $j$ is any legal state.
We notice that $f[i][j]$ is only related to $f[i  1][k]$, so we can use a rolling array to optimize the space complexity.
The time complexity is $O((m + n) \times 3^{2m})$, and the space complexity is $O(3^m)$. Here, $m$ and $n$ are the number of rows and columns of the grid, respectively.

class Solution { public int numOfWays(int n) { int mod = (int) 1e9 + 7; long f0 = 6, f1 = 6; for (int i = 0; i < n  1; ++i) { long g0 = (3 * f0 + 2 * f1) % mod; long g1 = (2 * f0 + 2 * f1) % mod; f0 = g0; f1 = g1; } return (int) (f0 + f1) % mod; } }

using ll = long long; class Solution { public: int numOfWays(int n) { int mod = 1e9 + 7; ll f0 = 6, f1 = 6; while (n) { ll g0 = (f0 * 3 + f1 * 2) % mod; ll g1 = (f0 * 2 + f1 * 2) % mod; f0 = g0; f1 = g1; } return (int) (f0 + f1) % mod; } };

class Solution: def numOfWays(self, n: int) > int: mod = 10**9 + 7 f0 = f1 = 6 for _ in range(n  1): g0 = (3 * f0 + 2 * f1) % mod g1 = (2 * f0 + 2 * f1) % mod f0, f1 = g0, g1 return (f0 + f1) % mod

func numOfWays(n int) int { mod := int(1e9) + 7 f0, f1 := 6, 6 for n > 1 { n g0 := (f0*3 + f1*2) % mod g1 := (f0*2 + f1*2) % mod f0, f1 = g0, g1 } return (f0 + f1) % mod }

function numOfWays(n: number): number { const mod: number = 10 ** 9 + 7; let f0: number = 6; let f1: number = 6; for (let i = 1; i < n; i++) { const g0: number = (3 * f0 + 2 * f1) % mod; const g1: number = (2 * f0 + 2 * f1) % mod; f0 = g0; f1 = g1; } return (f0 + f1) % mod; }