Comment on page

# 256 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.
The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs is the cost of painting house 0 with color red; costs is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.
Note: All costs are positive integers.

## Brute Force

The Idea: Build a tree. The root is initially going to begin with the costs of the first three color options for house 0. Then for each house that follows, we have 2 options from the parent house. Keep track of these and continue to build the tree until the final house is reached. The final level of the tree will contain the accumulative costs for every single kind of viable color combination. Return the minimum of these costs.
Complexity: O(3 * 2^(n-1)) time and space
import queue
class Solution:
def minCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
if not costs: return 0
n_rows = len(costs)
q = queue.Queue()
q.put({'cost': costs, 'color': 0, 'house': 0})
q.put({'cost': costs, 'color': 1, 'house': 0})
q.put({'cost': costs, 'color': 2, 'house': 0})
while not q.empty():
front = q.get()
if front['house'] + 1 < n_rows:
for color in range(0, 3):
if front['color'] != color:
q.put({'cost': front['cost'] + costs[front['house']+1][color],
'color': color, 'house': front['house'] + 1})
else:
break
min_cost = float('inf')
while not q.empty():
min_cost = min(min_cost, q.get()['cost'])
return min_cost

## Dynammic Programming

The Idea: Keep track of only three paths total rather than expanding 2 for every path as we've done in the previous approach. Depending on the color of the house, add the minimum of the remaining two options. We can prove why this works inductively. In the base case with `n_rows = 1`, we return the minimum of the costs. When `n_rows = 2`, then we can show that the best choice given one house color is going to be the minimum of the other house color options. For `n_row = 3` and above, just consider the accumulative cost from the previous row. This is equivalent to starting with the accumulative cost, and simply treating the next set as `n_row = 2`, which we've proved to be optimal.
Complexity: O(n*3) time and O(1) space
int minCost(vector<vector<int>>& costs) {
int n_rows = costs.size();
if (!n_rows) return 0;
for (int row = 1; row < n_rows; row++) {
costs[row] += min(costs[row-1], costs[row-1]);
costs[row] += min(costs[row-1], costs[row-1]);
costs[row] += min(costs[row-1], costs[row-1]);
}
return *min_element(costs[n_rows - 1].begin(), costs[n_rows - 1].end());
}