# 265. Paint House II

## LeetCode [265. Paint House II](https://leetcode-cn.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`
* `1 <= k <= 20`
* `1 <= costs[i][j] <= 20`

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

### Tags

Dynamic Programming

### Solution

The basic idea is inherited from LeetCode [256. Paint House](https://leetcode-cn.com/problems/paint-house/). However, when we need to calculate the minimum number for each cur\[i], the time overhead would be `O(k²)`. To save it from repeated minimum value computing, we obtain the the **two** smallest numbers in `pre` before we update `cur`. Let's say that the minimum value of `pre` is `first` and its index is `i`, and the last but one minimum number is called `second`. We can find that all elements apart from `cur[i]` share the same minimum value `first`, and the minimum value in terms of `cur[i]` is `second`. In this way, we manage to optimize the time complexity from `O(nk²)` to `O(nk)`.

### Complexity

* Time complexity: $$O(nk)$$
* Space complexity: $$O(k)$$

### Code

```go
type pair struct {
	num, idx int
}

func minCostII(costs [][]int) int {
	ans, cur, pre := 2147483647, make([]int, len(costs[0])), costs[len(costs)-1]
	for i := len(costs) - 2; i >= 0; i-- {
		copy(cur, costs[i])
		first, second := minTwo(pre)
		for j := 0; j < len(cur); j++ {
			if j != first.idx {
				cur[j] += first.num
			} else {
				cur[j] += second.num
			}
		}
		copy(pre, cur)
	}
	for _, n := range pre {
		if n < ans {
			ans = n
		}
	}
	return ans
}

func minTwo(nums []int) (pair, pair) {
	first, second := pair{2147483647, -1}, pair{2147483647, -1}
	for i, n := range nums {
		if n < first.num {
			second.num, second.idx = first.num, first.idx
			first.num, first.idx = n, i
		} else if n < second.num {
			second.num, second.idx = n, i
		}
	}
	return first, second
}
```
