Medium

Paint House

LAB

Given cost rows for red, blue, and green, return the minimum cost to paint all houses with adjacent houses using different colors.

EXAMPLES

Example 1

Input
{
  "costs": [
    [
      17,
      2,
      17
    ],
    [
      16,
      16,
      5
    ],
    [
      14,
      3,
      19
    ]
  ]
}

Output
10

FUNCTION SHAPE

costs: intMatrix→int

SOLUTION NOTE

For each house, try all colors except previous house's color. Take minimum.

Reveal reference solution +

pythonREFERENCE

def minCost(self, costs: List[List[int]]) -> int:
    n = len(costs)

    @cache
    def dp(i, color):
        if i == n:
            return 0
        return costs[i][color] + min(dp(i + 1, c) for c in range(3) if c != color)

    return min(dp(0, c) for c in range(3))

TimeO(n)

SpaceO(n)

Open on LeetCode ↗