Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/276.html
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:
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 givenn
andk
.
Algorithm
If either n == 0
or k == 0
, then it is impossible to paint the fence according to the requirement, so return 0.
Use dynamic programming. Create a 2D array dp
with n
rows and 2 columns, where
dp[i][1]
represents the number of ways to paint the fence’s firsti + 1
posts while thei
-th post has the same color as its previous post,- and
dp[i][0]
represents the number of ways to paint the fence’s firsti + 1
posts while thei
-th post doesn’t have the same color as its previous post.
Obviously, dp[0][0] = 0
and dp[0][1] = k
. For i > 0
, dp[i][0] = dp[i - 1][1]
since the current post has the same color as the previous post, and dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1)
since to select a color different to the previous post, there are k - 1
selections.
Finally, return dp[n - 1][0] + dp[n - 1][1]
.
Code
-
public class Paint_Fence { public static void main(String[] args) { Paint_Fence out = new Paint_Fence(); Solution s1 = out.new Solution(); Solution_noArray s2 = out.new Solution_noArray(); System.out.println(s1.numWays(3, 2)); // 6 System.out.println(s2.numWays(3, 2)); } class Solution { public int numWays(int n, int k) { if (n == 0 || k == 0) return 0; // `dp[i][0]` same color // `dp[i][1]` different color int[][] dp = new int[n][2]; dp[0][0] = 0; dp[0][1] = k; for (int i = 1; i < n; i++) { dp[i][0] = dp[i - 1][1]; // or else 3-posts the same color dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1); } return dp[n - 1][0] + dp[n - 1][1]; } } public class Solution_noArray { public int numWays(int n, int k) { if (n == 0) return 0; int same = 0, diff = k; for (int i = 2; i <= n; ++i) { int t = diff; diff = (same + diff) * (k - 1); same = t; } return same + diff; } } } ############ 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]; } }
-
// OJ: https://leetcode.com/problems/paint-fence/ // Time: O(N) // Space: O(1) class Solution { public: int numWays(int n, int k) { if (k == 1 && n >= 3) return 0; int dp[2] = {k, 0}; for (int i = 1; i < n; ++i) { int next[2] = {(k - 1) * (dp[0] + dp[1]), dp[0]}; swap(next, dp); } return dp[0] + dp[1]; } };
-
class Solution: def numWays(self, n: int, k: int) -> int: # `dp[i][0]` same color # `dp[i][1]` different color dp = [[0] * 2 for _ in range(n)] dp[0][1] = k for i in range(1, n): dp[i][0] = dp[i - 1][1] # same as previous, or else 3-posts the same color dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) * (k - 1) # not the same as previous return sum(dp[-1]) ############ class Solution(object): def numWays(self, n, k): """ :type n: int :type k: int :rtype: int """ if n > 2 and k == 1: return 0 if n < 2: return n * k pre = k * k ppre = k for i in range(2, n): tmp = pre pre = (k - 1) * (pre + ppre) ppre = tmp return pre
-
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] }