StaffDynamic Programming
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. That is, no two cells that share vertical or horizontal sides may 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 = 1Output
12There are 12 possible ways to paint a 1 x 3 grid while satisfying the adjacency rule.
Example 2
Input
n = 5000Output
30228214For n = 5000, the number of valid paintings modulo 10^9 + 7 is 30228214.
Constraints
- n == grid.length
- 1 <= n <= 5000