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
.
Example 1:
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
Solution: DP
dp[i][0] := # of ways to paint i rows with 2 different colors at the i-th row
dp[i][1] := # of ways to paint i rows with 3 different colors at the i-th row
dp[1][0] = dp[1][1] = 6
dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 2
dp[i][1] = dp[i-1][0] * 2 + dp[i-1][1] * 2
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int numOfWays(int n) { constexpr int kMod = 1e9 + 7; // dp[i][0] = # of ways to paint i rows with i-th row has 2 colors (e.g. 121) // dp[i][1] = # of ways to paint i rows with i-th row has 3 colors (e.g. 123) // dp[1][0] = dp[1][1] = 6. vector<vector<long>> dp(n + 1, vector<long>(2, 6)); for (int i = 2; i <= n; ++i) { // 121 => 2 colors x 3 {212, 232, 313}, 3 colors x 2 {213, 312} // 123 => 2 colors x 2 {212, 232}, 3 colors x 2 {231, 312} dp[i][0] = (dp[i - 1][0] * 3 + dp[i - 1][1] * 2) % kMod; dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1] * 2) % kMod; } return (dp[n][0] + dp[n][1]) % kMod; } }; |
Python3
1 2 3 4 5 6 7 8 9 |
# Author: Huahua class Solution: def numOfWays(self, n: int) -> int: kMod = 10**9 + 7 dp2, dp3 = 6, 6 for i in range(1, n): t2, t3 = dp2 * 3 + dp3 * 2, dp2 * 2 + dp3 * 2 dp2, dp3 = t2 % kMod, t3 % kMod return (dp2 + dp3) % kMod |
Solution 2: DP w/ Matrix Chain Multiplication
ans = {6, 6} * {{3, 2}, {2,2}} ^ (n-1)
Time complexity: O(logn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua class Solution { public: int numOfWays(int n) { constexpr long kMod = 1e9 + 7; vector<vector<long>> ans{{6, 6}}; // 1x2 vector<vector<long>> M{{3, 2},{2,2}}; // 2x2 auto mul = [kMod](const vector<vector<long>>& A, const vector<vector<long>>& B) { const int m = A.size(); // m * n const int n = B.size(); // n * p const int p = B[0].size(); vector<vector<long>> C(m, vector<long>(p)); for (int i = 0; i < m; ++i) for (int j = 0; j < p; ++j) for (int k = 0; k < n; ++k) C[i][j] += (A[i][k] * B[k][j]) % kMod; return C; }; --n; while (n) { if (n & 1) ans = mul(ans, M); // ans = ans * M; M = mul(M, M); // M = M^2 n >>= 1; } // ans = ans0 * M^(n-1) return (ans[0][0] + ans[0][1]) % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment