DP-9. Paint Fence

Problem

LeetCode 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.

Example:
Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:

post1 post2 post3
1 c1 c1 c2
2 c1 c2 c1
3 c1 c2 c2
4 c2 c1 c1
5 c2 c1 c2
6 c2 c2 c1

Explanation

I think this problem has a lot to do with math… specifically, probability.

In the first position, we have k possibilities. Then, in the second position, if we are the same as the previous position, we still have k possibilities; while if we are different as the previous position, we can have (k - 1) possibilities, so on the second postion, we totally have k + k * (k - 1) possibilities. So, we can see the positions afterwards also have the same pattern. The total possibilities are can be sum up by the same as the previous position and different as the previous position.

So, how to get the recurrence relation? As stated before, we need two array, separately representing the current position have the same color as the previous one and different from the previous one: same[n] and diff[n]
.
If the current position has the same color as the previous relation, it will have the same possibilities as the diff[i - 1]. Because only two consecutive same color is allowed. If the current position has the different color from the previous relation. It can be (k - 1) * diff[i - 1] + (k - 1) * same[i]. Because diff[i] can be different from the same[i - 1] or diff[i - 1], both are ok, so we should add them up.

Finally, we should add those two possibilities together.

A note

Do not forget to handle the corner case.
When either n or k is 0, return 0;
When n = 1, the result should just be k.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int numWays(int n, int k) {
if (n == 0 || k == 0) return 0;
if (n == 1) return k;

int[] same = new int[n];
int[] diff = new int[n];
same[0] = same[1] = k;
diff[0] = k;
diff[1] = k * (k - 1);

for (int i = 2; i < n; i++) {
same[i] = diff[i - 1];
diff[i] = (k - 1) * same[i - 1] + (k - 1) * diff[i - 1];
}

return same[n - 1] + diff[n - 1];
}
}