Paint Fence -- LeetCode

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.

思路：DP。

设p(i)表示从第一张海报到第i张海报的情况数。

初始情况：p(0) = 0，p(1) = k。

当n=2时，有两种情况：1）第二张海报的颜色与第一张不同，一共k * (k - 1)种情况；2）两张海报的颜色一样，一共k种情况。所以p(2) = k + k* (k - 1).

当n>2时，假设当前是第i张海报，此时有两种情况：1）第i张海报与前一张的颜色不同，一共是p(i - 1) * (k - 1)种情况; 2) 第i张海报与前一张的颜色一样，一共是p(i-2) * (k - 1)种情况。

所以p(i) = p(i-2)*(k-1) + p(i-1)*(k-1).

在实现时，我们并不需要用数组来记录所有的结果，我们只需要p(i-2)和p(i-1)的值，因此可以用变量slow来记录p(i-2)的值，用fast来记录p(i-1)的值。

 

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return n;
        if (n == 1) return k;
        int slow = k;
        int fast = slow + slow * (k - 1);
        for (int i = 3; i <= n; i++) {
            int cur = slow * (k - 1) + fast * (k - 1);
            slow = fast;
            fast = cur;
        }
        return fast;
    }
};