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.

reference: https://segmentfault.com/a/1190000005730444

Solution1：DP

思路：
Time Complexity: O(N) Space Complexity: O(N)

Solution2：DP Space Optimization

思路：
Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

class Solution {
    //State: f[i][j] is total number of ways we can paint the fence;
    // f[i][0]表示跟前面不一样颜色，f[i][1]表示跟前面一样颜色
    
    //Function: f[i][0] = f[i - 1][0] * k - 1 + f[i - 1][1] * (k - 1)
    //          f[i][1] = f[i - 1][0] + f[i - 1][1]
    
    //Initialize: f[0][0] = k, f[0][1] = k; f[1][0] = k * (k - 1), f[1][1] = k;
    //Result: f[n - 1][0] + f[n - 1][1];
    
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int[][] f = new int[n][2];
        //Initialize
        f[0][1] = f[1][1] = k;
        f[0][0] = k;
        f[1][0] = k * (k - 1);
        //f[i][0]表示跟前面不一样颜色，f[i][1]表示跟前面一样颜色
        for (int i = 2; i < n; i++) {
            //跟前面不一样颜色的话，在这轮有k - 1种可能性
            f[i][0] = f[i - 1][0] * (k - 1) + f[i - 1][1] * (k - 1);
            //跟前面一样颜色的话，在这轮有1种可能性，且前一轮不能与前前一轮一样颜色
            f[i][1] = f[i - 1][0];
        }
        
        return f[n - 1][0] + f[n - 1][1];
    }
}

Solution2 Code：

class Solution {
    // Save space to O(1) because it only cares about i - 1 and i
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int diff = k * (k - 1);
        int same = k;
        for (int i = 2; i < n; i++) {
            int tmp = diff;
            diff = (diff + same) * (k - 1);
            same = tmp;
        }
        return same + diff;
    }
}