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 nonnegative integers.
@tagdp
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 3posts 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/paintfence/ // 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(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