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;
    }
}