276. Paint Fence - jiejackyzhang/leetcode-note GitHub Wiki

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.

注意到题目是no more than， 因此允许两个相邻的是同样的颜色。

解题思路为Dynamic Programming。

对于一个post，它的颜色可以与前一个相同或不同，用两个数组differ_count，same_count来记录这两种情况。 对于differ_count[i]，可以用与i-1不同的颜色，即k-1种；对于same_count[i]，要用与i-1相同的颜色，但是要与i-2不同。

differ_count[i] = differ_count[i-1]*(k-1) + same_count[i-1]*(k-1);
same_count[i] = differ_count[i-1]

base cases为：

return k if n = 1
n = 2:
same_count[2] = k
differ_count[2] = k * (k-1)

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0)
            return 0;
        if (n == 1)
            return k;
        int same_count = k;
        int differ_count = k * (k - 1);
        for (int i = 3; i <= n; i++) {
            int temp = differ_count;
            differ_count = differ_count * (k - 1) + same_count * (k - 1);
            same_count = temp;
        }
        return same_count + differ_count;
    }
}