# 0265. Paint House II

<https://leetcode.com/problems/paint-house-ii>

## Description

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 an `n x k` cost matrix costs.

* 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...

Return *the minimum cost to paint all houses*.

**Example 1:**

```
**Input:** costs = [[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.
```

**Example 2:**

```
**Input:** costs = [[1,3],[2,4]]
**Output:** 5
```

**Constraints:**

* `costs.length == n`
* `costs[i].length == k`
* `1 <= n <= 100`
* `2 <= k <= 20`
* `1 <= costs[i][j] <= 20`

**Follow up:** Could you solve it in `O(nk)` runtime?

## ac

O(nk^2)

```java
class Solution {
    public int minCostII(int[][] costs) {
        // edge cases
        if (costs == null || costs.length == 0 || costs[0].length == 0) 
            return 0;

        int row = costs.length;
        int col = costs[0].length;
        for (int r = 1; r < row; r++) {
            for (int c = 0; c < col; c++) {
                int min = Integer.MAX_VALUE;  // min value from previous house
                for (int k = 0; k < col; k++) {
                    if (k == c) continue;  // avoid same color
                    min = Math.min(min, costs[r-1][k]);
                }
                costs[r][c] += min;  // update curr cell
            }
        }

        // check last row, get result
        int res = Integer.MAX_VALUE;
        for (int c = 0; c < col; c++) {
            res = Math.min(res, costs[row-1][c]);
        }

        return res;
    }
}

/*
1 2 3 4
4 5 6 7
7 8 9 10

*/
```

```java
class Solution {
    public int minCostII(int[][] costs) {
        // edge cases
        if (costs == null || costs.length == 0 || costs[0].length == 0) 
            return 0;

        int row = costs.length;
        int col = costs[0].length;
        int min1idx = -1, min2idx = -1;

        for (int r = 0; r < row; r++) {
            int tmpmin1 = -1, tmpmin2 = -1;

            for (int c = 0; c < col; c++) {

                if (r > 0) {  // skip first row
                    if (min1idx == c) {  // 1st min is same color, use 2nd color
                        costs[r][c] += costs[r-1][min2idx];  
                    } else {
                        costs[r][c] += costs[r-1][min1idx];  
                    }
                }

                // update 1st min and 2nd min
                if (tmpmin1 == -1 || costs[r][c] < costs[r][tmpmin1]) {
                    tmpmin2 = tmpmin1;
                    tmpmin1 = c;
                } else if (tmpmin2 == -1 || costs[r][c] < costs[r][tmpmin2]) {
                    tmpmin2 = c;
                }
            }
            min1idx = tmpmin1;
            min2idx = tmpmin2;
        }

        // check last row, get result
        int res = Integer.MAX_VALUE;
        for (int c = 0; c < col; c++) {
            res = Math.min(res, costs[row-1][c]);
        }

        return res;
    }
}

/*
from O(nk^2) to O(nk), keep 2 variables from previous step: 1st min, 2nd min
1 2 3 4
4 5 6 7
7 8 9 10

*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0265-paint-house-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.