Paint House I

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.

Note:
All costs are positive integers.

//dp[i][j]:minimum cost to paint first i houses with house i to be j color
//dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][j]
//given the color of house i
//find the min total cost to paint first i-1 houses
//0:red, 1:green, 2:blue
//time: O(nk) k: # of colors, n: # of houses
public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    int row = costs.length;
    int col = costs[0].length;
    int[][] dp = new int[row][col];
    //for house 0, dp[0][j] = costs[0][j]
    for (int j = 0; j < col; j++) {
        dp[0][j] = costs[0][j];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 0; j < col; j++) {
            int min = Integer.MAX_VALUE;
            //given the color of house i
            //find the min total cost to paint first i-1 houses
            for (int k = 0; k < col; k++) {
                if (k == j) {
                    continue;
                }
                min = Math.min(min, dp[i - 1][k]);
            }
            dp[i][j] = min + costs[i][j];
        }
    }
    int minCost = Integer.MAX_VALUE;
    //return min in last row
    for (int j = 0; j < col; j++) {
        minCost = Math.min(minCost, dp[row - 1][j]);
    }
    return minCost;
}

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    if (costs[0].length == 1) {
        return costs[0][0];
    }
    int n = costs.length;
    int k = costs[0].length;
    //dp 2d array.
    //minCost[i][j]: minimum cost to paint ith house with color j.
    int[][] minCost = new int[n][k];
    //minColor==i: for the current house, use ith color has smallest total value from house 0 ~ i
    int minColor = -1;

    //init first row(1st house)
    int minValue = Integer.MAX_VALUE;
    int secondMinValue = Integer.MAX_VALUE;
    for (int j = 0; j < k; j++) {
        minCost[0][j] = costs[0][j];
        if (minCost[0][j] < minValue) {
            //Important here!
            //if there is a new min, then we need to compare the old min with the secondMinValue
            secondMinValue = Math.min(secondMinValue, minValue);
            minValue = minCost[0][j];
            minColor = j;
        } else if (minCost[0][j] < secondMinValue) {
            secondMinValue = minCost[0][j];
        }
    }
    int preMinValue, preSecondMinValue, preMinColor;
    for (int i = 1; i < n; i++) {
        preMinColor = minColor;
        preMinValue = minValue;
        preSecondMinValue = secondMinValue;
        minColor = -1;
        minValue = Integer.MAX_VALUE;
        secondMinValue = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            //if minCost[i-1][j] is not the smallest
            if (j != preMinColor) {
                minCost[i][j] = preMinValue + costs[i][j];
            }
            //if minCost[i-1][j] is the smallest
            //then we can only use the second smallest one
            else {
                minCost[i][j] = preSecondMinValue + costs[i][j];
            }
            if (minCost[i][j] < minValue) {
                //Important here!
                //if there is a new min, then we need to compare the old min with the secondMinValue
                secondMinValue = Math.min(secondMinValue, minValue);
                minValue = minCost[i][j];
                minColor = j;
            } else if (minCost[i][j] < secondMinValue) {
                secondMinValue = minCost[i][j];
            }
        }
    }
    return minValue;
}

Share