> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/paint-house.md).

# Paint House

There are a row of `n` houses, each house can be painted with one of the three colors: red, blue or green. 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,** and you need to cost the least. Return the minimum cost.

The cost of painting each house with a certain color is represented by a `n` x `3` cost matrix. For example, `costs[0][0]` is the cost of painting house `0` with color red; `costs[1][2]` is the cost of painting house `1` with color green, and so on... Find the minimum cost to paint all houses.

**All costs are positive integers.**

#### Example

**Example 1:**

```
Input: [[14,2,11],[11,14,5],[14,3,10]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.
```

**Example 2:**

```
Input: [[1,2,3],[1,4,6]]
Output: 3
```

```java
public class Solution {
    public int minCost(int[][] costs) {
        if(costs.length==0||costs==null)
            return 0;
        Integer[][] dp = new Integer[costs.length][3];
        int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
        int minColor = -1;
        for (int i = 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
            if (costs[0][i] < min) {
                secondMin = min;
                min = costs[0][i];
                minColor = i;
            } else if (costs[0][i] < secondMin)
                secondMin = costs[0][i];
        }
        for (int i = 1; i < costs.length; i++) {
            int newMin = Integer.MAX_VALUE, newSecond = Integer.MAX_VALUE;
            int newColor = -1;
            for (int j = 0; j < 3; j++) {
                // If it is same as previous color(which holds min value)
                if (j == minColor)
                    dp[i][j] = costs[i][j] + secondMin;
                else
                    dp[i][j] = costs[i][j] + min;
                if (dp[i][j] < newMin) {
                    newSecond = newMin;
                    newMin = dp[i][j];
                    newColor = j;
                } else if (dp[i][j] < newSecond)
                    newSecond = dp[i][j];
            }
            min = newMin;
            secondMin = newSecond;
            minColor = newColor;
        }
        return min;
    }
}
```