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

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

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());
}