Number of Ways to Paint N x 3 Grid

Similar Problems:

- CheatSheet: LeetCode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #dynamicprogramming, #paintfence

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.

Input: n = 1 Output: 12 Explanation: There are 12 possible way to paint the grid as shown:

Example 2:

Input: n = 2 Output: 54

Example 3:

Input: n = 3 Output: 246

Example 4:

Input: n = 7 Output: 106494

Example 5:

Input: n = 5000 Output: 30228214

Constraints:

- n == grid.length
- grid[i].length == 3
- 1 <= n <= 5000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

## https://code.dennyzhang.com/number-of-ways-to-paint-n-3-grid ## Basic Ideas: dynamic programming ## ## 1 X 3 ## A B C ## ## 2 X 3 ## A B C ## D E F ## ## 0 1 2 ## 3 4 5 ## 6 7 8 ## 9 10 11 ## Complexity: Time O(n), Space O(1) class Solution(object): def numOfWays(self, n): """ :type n: int :rtype: int """ dp = [1]*12 mapping = [[1, 2, 4, 5, 10], [0, 3, 6, 8, 11], [0, 3, 6, 7], [1, 2, 7, 10], [0, 6, 8, 9], [0, 6, 7, 9, 10], [1, 2, 4, 5, 11], [2, 3, 5, 11], [1, 4, 9, 10], [4, 5, 8, 11], [0, 3, 5, 8, 11], [1, 6, 7, 9, 10]] for _ in range(n-1): dp2 = [0]*12 for i in range(12): for j in mapping[i]: dp2[j] += dp[i] for i in range(12): dp[i] = dp2[i] return sum(dp) % (10**9+7)