**Solution with discussion** https://discuss.leetcode.com/topic/77741/python-solution-with-detailed-explanation

**Paint House** https://leetcode.com/problems/paint-house/?tab=Description

**Memoization**

- min_cost[i,j]: minimum cost to paint house i to N-1 such that house i-1 was painted with color j.
- Base case: return 0 for painting house N (there are only N-1 houses)
- Initial case: pass -1 as color index for house index -1.

```
from collections import defaultdict
class Solution(object):
def helper(self, hi, ci, costs, cache):
if hi == len(costs):
return 0
elif hi in cache and ci in cache[hi]:
return cache[hi][ci]
else:
candidates = (i for i in range(3) if i != ci)
cache[hi][ci] = float('inf')
for c in candidates:
cache[hi][ci] = min(cache[hi][ci], costs[hi][c] + self.helper(hi+1,c, costs,cache))
return cache[hi][ci]
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if costs == []:
return 0
cache = defaultdict(dict)
return self.helper(0, -1, costs, cache)
```

**Dynamic Programming**

- min_cost[i,j]: minimum cost to paint house 0 to i such that house i was painted with color j.
- Base case: min_cost[0,j] = costs[0,j]

```
from collections import defaultdict
class Solution(object):
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if costs == []:
return 0
N, cache = len(costs), defaultdict(dict)
K = 3
for k in range(K):
cache[0][k] = costs[0][k]
for i in range(1,N):
for j in range(K):
cache[i][j], candidates = float('inf'), (k for k in range(K) if j != k)
for c in candidates:
cache[i][j] = min(cache[i][j], cache[i-1][c]+costs[i][j])
return min(cache[N-1][k] for k in range(K))
```

- We can reuse the costs table - No need to create new matrix for dp. The dp / costs matrix has house index on rows and colors as columns.

```
class Solution(object):
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if costs == []:
return 0
N = len(costs)
for i in range(1, N):
costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
return min(costs[N-1][0], costs[N-1][1], costs[N-1][2])
```