Paint House II

There are a row of n houses, each house can be painted with one of the k colors.

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 k cost matrix costs.

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

Return the minimum cost to paint all houses.

Example 1:

Input: costs = [[1,5,3],[2,9,4]]

Output:5

Explanation:

Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;

Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Example 2:

Input: costs = [[1,3],[2,4]]

Output:5

Constraints:

costs.length == n

costs[i].length == k

1 <= n <= 100

2 <= k <= 20

1 <= costs[i][j] <= 20

Approach 1: Memoization

Remembering that we already know how to solve this problem using memoization when k = 3 (check the Paint House Solution Article) if you can't remember how), let's think through some of the other possible values of k.

For this explanation, we'll call a way of painting the houses valid if, and only if, there are no adjacent houses painted the same color. We'll call an input valid if it is possible to paint the houses in a valid way. The test cases here on Leetcode are all valid inputs. In an interview however, you'd need to ensure that it is safe to assume that the input is always valid though.

If k = 0, then this means we have no colors. If there are no colors, it's probably reasonable to assume there are no houses either, i.e. n = 0.

In other words, the input is []. For this question here on Leetcode, this is a safe assumption.

In an interview though it could be a good idea to ask the interviewer whether or not the input is guaranteed to be valid.

For example, could you get a test case such as [[],[],[],[]]?

This would be k = 0 and n = 4.

Of course, this case doesn't make much sense, because we are supposed to be painting houses, but can't with no paint.

Either you'd be told it could never happen, or that you needed to do something special for it, such as returning -1.

If k = 1 (all houses have to be the same color), then it's probably safe to assume that n = 1.

Otherwise, the problem would be impossible to solve without breaking the adjacent color rule.

Again, this is a safe assumption here, but do consider asking the interviewer whether or not you could get an invalid input that had k = 1 and n > 1.

So, assuming that k = 1 and n = 1, the total cost will be the cost of painting that one house the only color available.

If k = 2 (there are two colors), then we know the problem is always solvable, because we can simply paint the houses alternating colors.

For example, when n = 5 and k = 2, here are the only 2 valid ways of painting the houses. Anything else would be invalid.

The answer will be the one that leads to the lowest cost.

It'd be easy to check both.

When k = 3, the problem is equivalent to Paint House.

In the Solution Article for that question, we worked through an example where n = 4.

[[17, 2, 17], [8, 4, 10], [6, 3, 19], [4, 8, 12]]

A good way to visualize all of the valid painting permutations is to use a tree.

Each root-to-leaf path represents one valid way of painting the houses.

The cheapest cost of painting the houses is, therefore, the root-to-leaf path with the lowest total sum of its nodes.

Say we have a paint function that takes 2 parameters: a house number and a color to paint that house.

The output is the total cost of painting that house and all the ones after it.

For example paint(1, red) would be the cost of painting house 1 red, along with the cost of painting the houses after it (taking into account restrictions caused by painting house 1 red).

Therefore the cheapest way of painting all the houses can be expressed as follows, where 0 is the first house.

min(paint(0, "red"), paint(0, "green"), paint(0, "blue"))

The paint function has a recursive implementation. costs refers to the input table.

    
def paint(i, color):
### BASE CASE ###
if i is the last house number:
    return costs[i][color]
### RECURSIVE CASE ###
lowest_cost = Infinity
for each next_color in ["red", "green", "blue"]:
    if next_color != color: # No adjacent houses can be same color.
        this_cost = costs[i][color] + paint(i + 1, next_color) # <- Recursive call
        lowest_cost = min(lowest_cost, this_cost)
return lowest_cost
    

The base case is where i refers to the last house. Painting the last house a particular color can be obtained from the costs table.

The recursive case is where we also need to consider the houses after i. It is obtained by looking up the cost of painting house i the given color (in the costs table) and then by determining the cost of painting the houses after it. The cost of painting the houses after requires making recursive paint calls to determine the cost of painting house i + 1 each of the 2 other colors and then finding the minimum of those 2 values.

This algorithm is inefficient though. There is a lot of repetition in the tree, meaning we're doing the same calculations over and over again. For example, the total cost of painting the second house blue will be the same regardless of whether the first house was red or green. For example, both these branches of the tree are identical.

This should also be apparent from the definition of the paint function. The parameters are simply a house number and a color. It doesn't require any information about where exactly in the tree it is.

To solve this problem, we add memoization to the paint function. Recall that memoization is where before returning an answer, the recursive function writes the answer into a dictionary with the input parameters as the key and the answer as the value. Then before doing a calculation, it checks whether or not that particular calculation has already been done. For the example above, the function would only calculate the cost of painting the second house blue once, and then the second time it would look it up in the dictionary.

Here is a visualization that shows the calculations that need to be done when using memoization. The brighter circles show where the function body runs, and the duller circles show where a lookup was done and the function immediately returned. These are the only times the function is called.

If this explanation wasn't thorough enough for you, then please check out the full Paint House Solution Article. In that article I go into a lot more depth about memoization and how this algorithm was derived.

The k > 3 case is really no different to this. The only difference is that instead of only considering 2 possible colors for the next house, we're considering k - 1 colors (all colors except for the color of the current house).

Algorithm:

Unlike the pseudocode above, we don't need to worry about the names of the colors. Instead, they are represented by numbers between 0 and k - 1. Additionally, we're also using memoization (lru_cache in Python, and a dictionary in Java).

    
        class Solution {
            private int n;    
            private int k;    
            private int[][] costs;
            private Map memo;
        
            public int minCostII(int[][] costs) {
                if (costs.length == 0) return 0;
                this.k = costs[0].length;
                this.n = costs.length;
                this.costs = costs;
                this.memo = new HashMap<>();
                int minCost = Integer.MAX_VALUE;
                for (int color = 0; color < k; color++) {
                    minCost = Math.min(minCost, memoSolve(0, color));
                }
                return minCost;
            }
        
            private int memoSolve(int houseNumber, int color) {
                // Base case: There are no more houses after this one.
                if (houseNumber == n - 1) {
                    return costs[houseNumber][color];    
                }
    
                // Memoization lookup case: Have we already solved this subproblem?
                if (memo.containsKey(getKey(houseNumber, color))) {
                    return memo.get(getKey(houseNumber, color));    
                }
    
                // Recursive case: Determine the minimum cost for the remainder.
                int minRemainingCost = Integer.MAX_VALUE;
                for (int nextColor = 0; nextColor < k; nextColor++) {
                    if (color == nextColor) continue;
                    int currentRemainingCost = memoSolve(houseNumber + 1, nextColor);
                    minRemainingCost = Math.min(currentRemainingCost, minRemainingCost);
                }
                int totalCost = costs[houseNumber][color] + minRemainingCost;
                memo.put(getKey(houseNumber, color), totalCost);
                return totalCost;
            }
                
            // Convert a house number and color into a simple string key for the memo.        
            private String getKey(int n, int color) {        
                return String.valueOf(n) + " " + String.valueOf(color);        
            }        
        }