1
class Solution:
2
    def minCost(
3
        self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
4
    ) -> int:
5
        @cache
6
        def dp(i, p, h):
7
            if (h > target) or (i == m and h != target):
8
                return inf
9
            if i == m:
10
                return 0
11
            if houses[i] != 0:
12
                return dp(i + 1, houses[i], h + int(p != houses[i]))
13

14
            best = inf
15
            for j, c in enumerate(cost[i], 1):
16
                best = min(best, dp(i + 1, j, h + int(p != j)) + c)
17
            return best
18

19
        res = dp(0, 0, 0)
20
        return res if res != inf else -1