256. Paint House

很简单的一道题

别忘了滚动数组的空间优化。

public class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length;
        int[][] f = new int[2][3];

        f[0][0] = costs[0][0];
        f[0][1] = costs[0][1];
        f[0][2] = costs[0][2];

        for (int i = 1; i < n; ++i) {
            f[i % 2][0] = Math.min(f[(i - 1) % 2][1], f[(i - 1) % 2][2]) + costs[i][0];
            f[i % 2][1] = Math.min(f[(i - 1) % 2][0], f[(i - 1) % 2][2]) + costs[i][1];
            f[i % 2][2] = Math.min(f[(i - 1) % 2][1], f[(i - 1) % 2][0]) + costs[i][2];
        }
        return Math.min(f[(n - 1) % 2][0], Math.min(f[(n - 1) % 2][1], f[(n - 1) % 2][2]));
    }
}

276. Paint Fence

这题目有点阴啊，是我大意了一刚。

....no more than two adjacent fence posts have the same color...

反复检查了好几遍觉得代码没问题，答案就是不对，发现把题读错了。

其实这题和 House robber 还有 Fibonacci Number 非常像， 都是 T(n) 取决于 T(n - 1) 和 T(n - 2)，在 House Robber 里，我们在取值上有一个连续性的制约：不能偷位置连续的房子；在这题里，我们刷当前位置的时候，也有颜色上的制约，我们需要的是做些思考，把这个制约找出来。

在刷第 n 块栅栏颜色的时候，要么要和 n - 1 的颜色不一样，要么和 n - 2 的颜色不一样。

满足 “颜色不一样” 的选择，显然是 k - 1 种，于是

T[n] = (k - 1) * (T[n - 1] + T[n - 2]);

public 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[] f = new int[3];
        f[0] = 0;
        f[1] = k;
        f[2] = k * k;

        for (int i = 3; i <= n; ++i) {
            f[i % 3] = (f[(i - 1) % 3] + f[(i - 2) % 3]) * (k - 1);
        }
        return f[n % 3];
    }
}

265. Paint House II

O(n k k) 的算法非常直观，顺着LC256的思路就行了。