# DP solution in Java, O(nk^2)

• This problem can be solved using dynamic programming:

let `d[i][k]` be the minimum cost of painting houses from `0` to `i`, assuming `i`th 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;
}
}``````

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