# 256. Paint House

## LeetCode [256. Paint House](https://leetcode-cn.com/problems/paint-house/)

### Description

There is a row of `n` houses, where each house can be painted one of 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.

The cost of painting each house with a certain color is represented by an `n x 3` cost matrix `costs`.

* For example, `costs[0][0]` is the cost of painting house `0` with the color red; `costs[1][2]` is the cost of painting house 1 with color green, and so on...

Return *the minimum cost to paint all houses*.

**Example 1:**

```
Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
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: costs = [[7,6,2]]
Output: 2
```

**Constraints:**

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

### Tags

Dynamic Programming

### Solution

Start from the last but one element of `costs`. In terms of the current house `cur = costs[i]`, each element `cur[i] = min(pre[0..i-1, i+1, ...])` where `pre`, initialized with `costs[-1]`, is the last `cur`.

Though we can modify elements in-place, we solve this problem with extra `O(1)` space in case that other functions require this input variable.

### Complexity

* Time complexity: $$O(n)$$, given that there is always 3 colors, we only consider the loop;
* Space complexity: $$O(1)$$, 6 variables.

### Code

```go
func minCost(costs [][]int) int {
	pre := costs[len(costs)-1]
	for i := len(costs) - 2; i >= 0; i-- {
		cur := []int{costs[i][0], costs[i][1], costs[i][2]}
		cur[0] += min(pre[1], pre[2])
		cur[1] += min(pre[0], pre[2])
		cur[2] += min(pre[0], pre[1])
		pre = cur
	}
	return min(min(pre[0], pre[1]), pre[2])
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
```

## Reference

1. [粉刷房子](https://leetcode-cn.com/problems/paint-house/solution/fen-shua-fang-zi-by-leetcode/)