276. 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.

Note:
n and k are non-negative integers.

链接： http://leetcode.com/problems/paint-fence/

3/6/2017

抄别人答案。最大的问题：审题不清，题目中说最多2个相邻的可以用同一个颜色。

还有用dp问题，把中间过程想明白就好了。主要分析当前量和前一个量，（有时候需要前两个量），但是绝对不要复杂化从头想。最开始初始化要准确，但是确定了就是确定了，不要影响到每层的思路。

public int numWays(int n, int k) {
    if (n <= 0 || k <= 0) return 0;
    if (n == 1) return k;

    int sameColorLastTwo = k; // initialize meaning: #0 & #1 use the same color, choice number: k
    int diffColorLastTwo = k * (k - 1); // initialize meaning: #0 & #1 use different colors, choice number: k(k-1)

    for (int i = 2; i < n; i++) {
        int tmp = sameColorLastTwo;
        sameColorLastTwo = diffColorLastTwo;
        diffColorLastTwo = (tmp + diffColorLastTwo) * (k - 1);
    }
    return sameColorLastTwo + diffColorLastTwo;
}