# 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 given n and k.

# 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] represents the number of ways to paint the fence’s first i + 1 posts while the i-th post has the same color as its previous post,
• and dp[i] represents the number of ways to paint the fence’s first i + 1 posts while the i-th post doesn’t have the same color as its previous post.

Obviously, dp = 0 and dp = k. For i > 0, dp[i] = dp[i - 1] since the current post has the same color as the previous post, and dp[i] = (dp[i - 1] + dp[i - 1]) * (k - 1) since to select a color different to the previous post, there are k - 1 selections.

Finally, return dp[n - 1] + dp[n - 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] same color
// dp[i] different color
int[][] dp = new int[n];
dp = 0;
dp = k;
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1]; // or else 3-posts the same color
dp[i] = (dp[i - 1] + dp[i - 1]) * (k - 1);
}
return dp[n - 1] + dp[n - 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];
dp = k;
for (int i = 1; i < n; ++i) {
dp[i] = (dp[i - 1] + dp[i - 1]) * (k - 1);
dp[i] = dp[i - 1];
}
return dp[n - 1] + dp[n - 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 = {k, 0};
for (int i = 1; i < n; ++i) {
int next = {(k - 1) * (dp + dp), dp};
swap(next, dp);
}
return dp + dp;
}
};

• class Solution:
def numWays(self, n: int, k: int) -> int:
# dp[i] same color
# dp[i] different color
dp = [ * 2 for _ in range(n)]
dp = k
for i in range(1, n):
dp[i] = dp[i - 1] # same as previous, or else 3-posts the same color
dp[i] = (dp[i - 1] + dp[i - 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 = k
for i := 1; i < n; i++ {
dp[i] = (dp[i-1] + dp[i-1]) * (k - 1)
dp[i] = dp[i-1]
}
return dp[n-1] + dp[n-1]
}