April 17, 2020 ### 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 colours: RedYellow 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`.

### Solution:

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)

Similarly

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``````

Credit: leetcode, hiclipart

Recent Posts
Categories
Archive
Tags