# 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\[0]\[0] is the cost of painting house 0 with color red; costs\[1]\[2] 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

```python
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[0][0], 'color': 0, 'house': 0})
        q.put({'cost': costs[0][1], 'color': 1, 'house': 0})
        q.put({'cost': costs[0][2], '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

```cpp
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][0] += min(costs[row-1][1], costs[row-1][2]);
        costs[row][1] += min(costs[row-1][0], costs[row-1][2]);
        costs[row][2] += min(costs[row-1][0], costs[row-1][1]);
    }
    return *min_element(costs[n_rows - 1].begin(), costs[n_rows - 1].end());
}
```


---

# 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://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/256-paint-house.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.