painthouse2

gistfile1.txt

http://buttercola.blogspot.com/2015/09/leetcode-paint-house-ii.html
public class Solution {
    /*
    public int minCostII(int[][] costs) {
            if(costs == null || costs.length == 0)
            return 0;
        int n = costs.length;
        int m = costs[0].length;
        int[][] dp = new int[n][m];
        //initialization 
        for (int i=0; i < m; i++) {
            dp[0][i] = costs[0][i];
        }
        for(int i=1; i < n; i++) {
            for(int j=0; j < m; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for(int k=0; k < m; k++) {
                    if (j != k) {
                        dp[i][j] = Math.min(dp[i-1][k] + costs[i][j], dp[i][j]);
                    }
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i=0; i < m; i++) {
            res = Math.min(res, dp[n-1][i]);
        }
        return res;
    }
    */
    public int minCostII(int[][] costs) {
        if(costs == null || costs.length == 0)
            return 0;
        int n = costs.length;
        int m = costs[0].length;
        int[][] dp = new int[n][m];
        for(int i=0; i < n; i++) {
            for(int j=0; j < m; j++) {
                dp[i][j] = -1;
            }
        }
        for(int i=0; i < m; i++) {
            dp[0][i] = costs[0][i];
        }
        int min = Integer.MAX_VALUE;
        for(int i=0; i < m; i++) {
            min = Math.min(min, recurse(costs, dp, n-1, i, m));
        }
        return min;
    }
    public int recurse(int[][] costs, int[][] dp, int currW, int prevColor, int m) {
        if (currW < 0)
            return 0;        
        if (dp[currW][prevColor] != -1) {
            return dp[currW][prevColor];
        }
        int min = Integer.MAX_VALUE;
        for(int i=0; i < m; i++) {
            if (i != prevColor) {
                   min = Math.min(recurse(costs, dp, currW-1, i, m) + costs[currW][prevColor],min);
            }
        }
        dp[currW][prevColor] = min;
        return min;
    }
    
}