Leetcode - Paint Fence

Screenshot from 2016-02-23 20:57:00.png

My code:

public class Solution {
    public int numWays(int n, int k) {
        int[] dp = {0, k, k * k, 0};
        if (n <= 2)
            return dp[n];
        for (int i = 2; i < n; i++) {
            dp[3] = (k - 1) * (dp[1] + dp[2]);
            dp[1] = dp[2];
            dp[2] = dp[3];
        }
        return dp[3];
    }
}

这道题目居然是简单的题目。我真的做不出来。
DP的题目我没有能做出来的。我已经被打败了。

为什么要考这些恶心的题目？我们是数学家吗？
我们是程序员啊！！！！

为什么要花大量的时间在这上面！为什么！

思路：
cite from others

因为题目要求是不超过两个相邻的栅栏有同样颜色，所以可以把题目分解一下：设T(n)
为符合要求的染色可能总数，S(n)
为最后两个相邻元素为相同颜色的染色可能数，D(n)
为最后两个相邻元素为不同颜色的染色可能数。显然D(n) = (k - 1) * (S(n-1) + D(n-1))
S(n) = D(n-1)
T(n) = S(n) + D(n)
带入化简一下得出：T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2

其实可以有更简单的方法，涂到第 n 个的可能总数为** ①** 与 n-1 时的不同可能数，即(k-1)T(n-1)；加上 ② 与 n-1 时的相同可能数，因为连续相同不能超过两个，第 n 和 n-1 个的颜色和第 n-2 个肯定不同，所以与 n-1 时的相同数必定等于 n-2 时的不同可能数，即(k-1)T(n-2) ，于是有：
T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2

于是递推式有了，把T(1) and T(2) 求出来，就可以进行递推了。

http://massivealgorithms.blogspot.com/2015/06/google-interview-fence-painter-iteye.html
https://segmentfault.com/a/1190000003790650

到底还需不需要把时间浪费在这上面？？？

Anyway, Good luck, Richardo!

My code:

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

同样没做出来。

reference:
https://discuss.leetcode.com/topic/23426/o-n-time-java-solution-o-1-space/2

Anyway, Good luck, Richardo! -- 09/21/2016