Paint House

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Similar to House Robber, where for each house, you have the choice to rob the house or move on to the next one, in this question:
  • When you paint a house a color, you can’t paint the next house that same color.
• Therefore, with Top Down, just make sure you don’t do that by passing in the index of the house whose color you shouldn’t paint.
• Since it’s RGB, say “don’t paint the color with index 0” on the next recursion, thereby ensuring that you don’t do what isn’t necessary.
• For bottom up:
  • Bottom is the first house.
  • You are asking:
    • If I pick red, what is the optimal choice from the previous house? It is the optimal of all the green and all the blue choices!

Complexity

Runtime

• $O(N^2)$
  • There are N houses
  • For each house, there are at most 3 choices (R, G, or B).
  • For each house, you have to consider every other house.

Space

• $O(N)$ since there are a total of N houses (one house for each recursive call).

Code

Bottom Up

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        r_opt, g_opt, b_opt = 0, 0, 0
        for r, g, b in costs:
            r_opt, g_opt, b_opt = r + min(g_opt, b_opt) \
                                , g + min(r_opt, b_opt) \
                                , b + min(r_opt, g_opt)
        return min(r_opt, g_opt, b_opt)

• Bottom is the first house

Top Down

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        @cache
        def r(house_idx, skip_color_idx):
            if house_idx < 0:
                return 0
            
            min_cost = inf
            for color_idx, color in enumerate(costs[house_idx]):
                if color_idx != skip_color_idx:
                    min_cost = min(min_cost, color + r(house_idx - 1, color_idx))
            return min_cost
 
        return r(len(costs) - 1, -1)

• Top is the last house that was painted.

Notes

Cards

START Basic Front: Paint House Back: If I pick a color, I wish to pick the optimal choice from the previous house, not including my color.

END

---

References

• Paint House