Description#
You are painting a fence of n
posts with k
different colors. You must paint the posts following these rules:
- Every post must be painted exactly one color.
- There cannot be three or more consecutive posts with the same color.
Given the two integers n
and k
, return the number of ways you can paint the fence.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0276.Paint%20Fence/images/paintfenceex1.png)
Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.
Example 2:
Input: n = 1, k = 1
Output: 1
Example 3:
Input: n = 7, k = 2
Output: 42
Constraints:
1 <= n <= 50
1 <= k <= 105
- The testcases are generated such that the answer is in the range
[0, 231 - 1]
for the given n
and k
.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
| class Solution:
def numWays(self, n: int, k: int) -> int:
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = k
for i in range(1, n):
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)
dp[i][1] = dp[i - 1][0]
return sum(dp[-1])
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int numWays(int n, int k) {
int[][] dp = new int[n][2];
dp[0][0] = k;
for (int i = 1; i < n; ++i) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1);
dp[i][1] = dp[i - 1][0];
}
return dp[n - 1][0] + dp[n - 1][1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int numWays(int n, int k) {
vector<vector<int>> dp(n, vector<int>(2));
dp[0][0] = k;
for (int i = 1; i < n; ++i) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1);
dp[i][1] = dp[i - 1][0];
}
return dp[n - 1][0] + dp[n - 1][1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func numWays(n int, k int) int {
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 2)
}
dp[0][0] = k
for i := 1; i < n; i++ {
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) * (k - 1)
dp[i][1] = dp[i-1][0]
}
return dp[n-1][0] + dp[n-1][1]
}
|