Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/276.html
276 Paint Fence
There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.
Note:
n and k are non-negative integers.
@tag-dp
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
Java
-
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; } } }
-
// 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 = [[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]) ############ 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