Hard

Paint House II

LAB

Given costs for k colors per house, return the minimum cost to paint all houses with adjacent houses using different colors.

EXAMPLES

Example 1

Input
{
  "costs": [
    [
      1,
      5,
      3
    ],
    [
      2,
      9,
      4
    ]
  ]
}

Output
5

FUNCTION SHAPE

costs: intMatrix→int

SOLUTION NOTE

O(k²) becomes O(k) using prefix/suffix min. For color c, min of other colors = min(prefix[c-1], suffix[c+1]).

Reveal reference solution +

pythonREFERENCE

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

    @cache
    def prefix_min(i, c):
        if c < 0: return float('inf')
        return min(prefix_min(i, c - 1), dp(i, c))

    @cache
    def suffix_min(i, c):
        if c >= k: return float('inf')
        return min(dp(i, c), suffix_min(i, c + 1))

    @cache
    def dp(i, c):
        if i == n: return 0
        return costs[i][c] + min(prefix_min(i + 1, c - 1), suffix_min(i + 1, c + 1))

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

TimeO(n × k)

SpaceO(n × k)

Open on LeetCode ↗