StaffDynamic Programming
Painting a Grid With Three Different Colors
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 10^9 + 7.
Example 1
Input
m = 1, n = 1Output
3There are 3 possible colorings for a single cell: red, green, or blue.
Example 2
Input
m = 1, n = 2Output
6There are 6 valid ways to color two adjacent cells with different colors.
Constraints
- 1 <= m <= 5
- 1 <= n <= 1000