

Multiple States IX

Description

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.

Question Link

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

Example I

Input: [[1,5,3],[2,9,4]]
Output: 5
Explanation: Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5; Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Questions

• LeetCode - 265. Paint House II

Transform Function

if(k != i) dp[i][j] = Math.min(dp[i][j], costs[j][i] + dp[k][j - 1]);

Solution I

class Solution {
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) return 0;
        int n = costs.length, m = costs[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int[] row: dp) Arrays.fill(row, Integer.MAX_VALUE);
        for(int i = 0; i <= m; i++) dp[i][0] = 0;


        for(int j = 1; j <= n; j++) {
            for(int i = 1; i <= m; i++) {
                for(int k = (j == 1 ? 0 : 1); k <= m; k++) {
                    if(k != i) dp[i][j] = Math.min(dp[i][j], costs[j - 1][i - 1] + dp[k][j - 1]);
                }
            }
        }

        int res = Integer.MAX_VALUE;
        for(int i = 0; i <= m; i++) res = Math.min(dp[i][n], res);
        return res;
    }
}

Optimized

c = cost[i] + (last == i ? min2 : min1);

Solution II

class Solution {
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) return 0;
        int min1 = 0, min2 = 0, last = -1;
        for(int[] cost : costs) {
            int curMin1 = Integer.MAX_VALUE;
            int curMin2 = Integer.MAX_VALUE;
            int cur = -1;
            for(int i = 0; i < cost.length; i++) {
                int c = cost[i] + (last == i ? min2 : min1);
                if(c < curMin1) {
                    curMin2 = curMin1;
                    cur = i;
                    curMin1 = c;
                }else if(c < curMin2) {
                    curMin2 = c;
                }
            }
            min1 = curMin1;
            min2 = curMin2;
            last = cur;
        }

        return min1;
    }
}