# Paint House II

This page explains Java solution to problem `Paint House II` using `Dynamic Programming` algorithm.

## Problem Statement

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.

Example 1:

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.

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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;
}
}
``````

## Time Complexity

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)