https://leetcode.com/problems/paint-house

There are a row ofnhouses, 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 anx3cost 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.

Note:
All costs are positive integers.

Constraints:

costs are positive

method 1: intuitive dfs ==> time limit exceeded

    public int minCost(int[][] costs) {
        // -1 means no color left
        return dfs(costs, 0, -1);
    }

    private int dfs(int[][] costs, int start, int color) {
        if (start == costs.length) {
            return 0;
        }

        int min =  Integer.MAX_VALUE;
        for (int i = 0 ; i < 3; ++i) {
            if (color == i) {
                continue;
            }

            int need = costs[start][i] + dfs(costs, start + 1, i);
            min = Math.min(need, min);
        }
        return min;
    }

method 2: memorization

public class Solution {
    Integer[][] colorCost;
    public int minCost(int[][] costs) {
        // -1 means no color left
        int n = costs.length;
        colorCost = new Integer[n][3];
        return dfs(costs, 0, -1);
    }

    private int dfs(int[][] costs, int start, int color) {
        if (start == costs.length) {
            return 0;
        }

        if (color >= 0 && colorCost[start][color] != null) {
            return colorCost[start][color];
        }

        int min =  Integer.MAX_VALUE;
        for (int i = 0 ; i < 3; ++i) {
            if (color == i) {
                continue;
            }

            int need = costs[start][i] + dfs(costs, start + 1, i);
            min = Math.min(need, min);
        }
        if (color >= 0) colorCost[start][color] = min;
        return min;
    }
}

method 3: DP

public class Solution {

    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        int n = costs.length;

        // dp - no need initialized
        int[][] dp = new int[n+1][3];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < 3; ++j) {
                dp[i][j] = Math.min(dp[i+1][(j+1)%3], dp[i+1][(j+2)%3]) + costs[i][j];
            }
        }
        return minThree(dp[0][0], dp[0][1], dp[0][2]);
    }

    private int minThree(int a, int b, int c) {
        if (a < b) {
            return a < c ? a : c;
        } else {
            return b < c ? b : c;
        }
    }
}

依然老套路