Paint Fence

这个居然是easy题…这个dp真的有点难难度. 首先观察第i个可涂的颜色, 可以涂和i-1一样, 也可以不一样, 一样是k-1个涂法, 不一样呢? 不一样的话, 因为不能三个连续一样, 那么如果和前边一个不一样, 就要保证前边两个是一样的, 换句话说, 就是和i-2的不一样, 那么也是k-1个….这个很难想到..

class Solution {
    public int numWays(int n, int k) {
        if(n == 0)
            return 0;
        if(n == 1)
            return k;
        if(n == 2)
            return k*k;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = k;
        dp[2] = k*k;
        for(int i = 3; i <= n; i++) {
            dp[i] += dp[i-1] * (k - 1); // numbers of same ways for i pos
            dp[i] += dp[i-2] * (k - 1); // numbers of diff ways for i pos
        }
        return dp[n];
    }
    
}