Leetcode - Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

[分析]
动态规划题目，我习惯于从目的倒推中间过程，最后一家house选用什么颜色能使总花费最小呢，假设知道前面第 N - 1家使用不同颜色时的总花费，那问题就解决了，因此中间计算需要存储的信息dp[i][j] 表示第 i 家选用 颜色 j 时 0 - i家house所需的最小花费，递推式见代码。

public class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0)
            return 0;
        int N = costs.length;
        int[][] dp = new int[2][3];
        int prev = 0, curr = 1;
        for (int i = 0; i < N; i++) {
            prev = curr;
            curr = 1 - curr;
            dp[curr][0] = Math.min(dp[prev][1], dp[prev][2]) + costs[i][0];
            dp[curr][1] = Math.min(dp[prev][0], dp[prev][2]) + costs[i][1];
            dp[curr][2] = Math.min(dp[prev][0], dp[prev][1]) + costs[i][2];
        }
        return Math.min(dp[curr][0], Math.min(dp[curr][1], dp[curr][2]));
    }
}