DP solution in Java, O(nk^2)


  • 0
    A

    This problem can be solved using dynamic programming:

    let d[i][k] be the minimum cost of painting houses from 0 to i, assuming ith house is painted in color k.
    That means:

    1. d[0][j] = costs[0][j] for all j = 0 to k-1

    2. d[i][j] = ( min(d[i-1][c]), c = 0 to k-1, c!=j ) + costs[i][j].

    The result is min ( d[n-1][j] ), j = 0 to k-1.

    It can be implemented like that:

    public class Solution {
        public int getMinCostExceptColorK(int[] d, int k){
            int min=Integer.MAX_VALUE;
            for (int i=0; i<d.length; ++i){
                if (i==k) continue;
                min=Math.min(d[i], min);
            }
            return min;
        }
        
        public int minCostII(int[][] costs) {
            int n=costs.length;
            if (n==0) return 0;
            int k=costs[0].length;
            int[][] d=new int[n][k];
            for (int i=0; i<k; ++i){
                d[0][i]=costs[0][i];
            }
            for (int i=1; i<n; ++i){
                for(int j=0; j<k; ++j){
                    d[i][j]=getMinCostExceptColorK(d[i-1], j)+costs[i][j];
                }
            }
            int min=d[n-1][0];
            for (int i=1; i<k; ++i){
                min=Math.min(min, d[n-1][i]);
            }
            return min;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.