This page explains Java solution to problem Paint House II
using Dynamic Programming
algorithm.
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.
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.
package com.vc.hard;
class PaintHouseIi {
public int minCostII(int[][] costs) {
if(costs == null || costs.length == 0) return 0;
int n = costs.length;
for(int row = 1; row < n; row++) {
//Find two minimum elements from prevRow
int minFirstIndex = -1;
int minSecondIndex = -1;
for(int col = 0; col < costs[0].length; col++) {
int cost = costs[row - 1][col];
if(minFirstIndex == -1 || cost < costs[row - 1][minFirstIndex]) {
minSecondIndex = minFirstIndex;
minFirstIndex = col;
}
else if(minSecondIndex == -1 || cost < costs[row - 1][minSecondIndex]) {
minSecondIndex = col;
}
}
//Find minium in current column based on minimum on previous column
for(int col = 0; col < costs[0].length; col++) {
if(col == minFirstIndex) {
costs[row][col] += costs[row - 1][minSecondIndex];
}
else {
costs[row][col] += costs[row - 1][minFirstIndex];
}
}
}
int res = Integer.MAX_VALUE;
for(int col = 0; col < costs[0].length; col++) {
res = Math.min(res, costs[n - 1][col]);
}
return res;
}
}
O(N * K) Where
N is total number of houses in an input array
K is total number of colors in an input array
O(1)