You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.
Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: m = 1, n = 1 Output: 3 Explanation: The three possible colorings are shown in the image above.
Example 2:
Input: m = 1, n = 2 Output: 6 Explanation: The six possible colorings are shown in the image above.
Example 3:
Input: m = 5, n = 5 Output: 580986
Constraints:
1 <= m <= 51 <= n <= 1000We will use dynamic programming to solve this problem by first focusing on a single column. Each column can have certain valid color patterns that adhere to the rules -- no two adjacent cells have the same color. We will precompute these valid patterns and then extend this to multiple columns using dynamic programming.
The core idea is to calculate the number of ways to fill the grid up to each column, given the pattern of the previous column. This involves considering all possible compatible patterns for new columns based on previous ones. We store results in a DP table and utilize modulo operations to avoid overflow.
This C code calculates the number of ways to color the grid using dynamic programming. The two variables 'color3' and 'color2' store the number of ways to paint a column in a 3-color pattern and a 2-color pattern respectively. The loops iterate over columns and update these patterns based on previous columns, respecting the color rules.
C++
Java
Python
C#
JavaScript
The time complexity is O(n), and the space complexity is O(1) as we only use a fixed amount of extra space.
This method involves using a memoization table to record transitions between valid patterns. The key is to represent each valid column configuration in a way that captures all legal states, and keep track of transitions between states to avoid redundant calculations. This dramatically reduces the computation complexities by caching evaluations.
By using bitwise operations or effectively encoding states, patterns can be compactly stored, leveraging recursion with memoization to efficiently compute the total number of colorings.
In this C solution, a recursive function is used, coupled with a memoization table (a 2-dimensional array) to store previous results. The 'isValidState' function checks if a particular configuration complies with color rules.
C++
Java
Python
C#
JavaScript
Space and time complexities can be near O(n * 3^m) due to memoization and reduced redundant calculations.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Pattern Compression | The time complexity is O(n), and the space complexity is O(1) as we only use a fixed amount of extra space. |
| Optimized Dynamic Programming with Memoization | Space and time complexities can be near O(n * 3^m) due to memoization and reduced redundant calculations. |
Walls and Gates - Multi-Source BFS - Leetcode 286 - Python • NeetCode • 94,114 views views
Watch 9 more video solutions →Practice Painting a Grid With Three Different Colors with our built-in code editor and test cases.
Practice on FleetCode