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.

Ideas: no more than two是指最多有两个fence的颜色相同。 那么可以想象dp1[i]代表i和i-1颜色相同的方法数量，dp2[i]代表i和i-1颜色不同的方法数量 dp1[i] = dp2[i-1]; dp2[i] = dp1[i-1] (k-1) + dp2[i-1] (k-1) = (dp2[i-2]+dp2[i-1]) * (k-1);

简化后如code

Code:

public int numWays(int n, int k) {
    if(n == 0) return 0;
    else if(n == 1) return k;
    int diffColorCounts = k*(k-1);
    int sameColorCounts = k;
    for(int i=2; i<n; i++) {
        int temp = diffColorCounts;
        diffColorCounts = (diffColorCounts + sameColorCounts) * (k-1);
        sameColorCounts = temp;
    }
    return diffColorCounts + sameColorCounts;
}