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 colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).
You are 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.
This is a DP (Dynamic Programming) problem. We calculate the simple problems and store their results. Using the results of the simple problems we solve the given bigger problem!
Let's start from one row grid
1 x 3 grid:
Then it boils down to a simple permutation problem. We can paint this in 27 ways (3 x 3 x 3) but only 12 of them will be valid as per the problem description. The possible color combinations are shown in the above figure. We can approach this as
Number of ways using two colors: 121, 212, 131, 313, 232, 323
Number of ways using three colors: 123, 132, 213, 231, 312, 321
2 x 3 grid:
We've already solved the first row. Now we solve for the second row
Assume first row has 121:
- Using two colors: 212, 313, 232
- Using three colors: 123, 321
Assume first row has 123:
- Using two colors: 212, 232
- Using three colors: 312, 231
For ith of row we can write a recursive euation as follows.
Note: C2i, C3i, represents number of ways possible for ith row with two colors and three colors respectivelt.
C2i (no of ways using two colors) = (C2i-1 x 3) + (C3i-1 x 2)
C3i (no of ways using three colors) = (C2i-1 x 2) + (C3i-1 x 2)
In case of i=2, C2i-1 = C3i-1 = 6
class Solution: def numOfWays(self, n: int) -> int: # Ways to color first row using 3 colors c3 = 6 # ways to color first row using 2 colors c2 = 6 mod = 10 ** 9 + 7 for i in range(1, n): temp2 = c3 * 2 + c2 * 3 temp3 = c3 * 2 + c2 * 2 c3 = temp3 % mod c2 = temp2 % mod return (c3 + c2) % mod