text: from functools import lru_cache
  from typing import List, Union
  
  
  # Top-down (Memoization)
  # TC: O(M * N * N * target); SC: O(M * N * target)
  def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
      @lru_cache(None)
      def dp(i: int, j: int, k: int) -> Union[float, int]:
          if k > target:
              return float('inf')
  
          if i == m:
              if k == target:
                  return 0
              else:
                  return float('inf')
  
          if houses[i]:
              return dp(i + 1, houses[i], k + (houses[i] != j))
  
          ans = float('inf')
          for idx, cst in enumerate(cost[i]):
              ans = min(ans, cst + dp(i + 1, idx + 1, k + (idx + 1 != j)))
  
          return ans
  
      res = dp(0, 0, 0)
      return res if res != float('inf') else -1
  
  