<p>There is a row of <code>m</code> houses in a small city, each house must be painted with one of the <code>n</code> colors (labeled from <code>1</code> to <code>n</code>), some houses that have been painted last summer should not be painted again.</p>

<p>A neighborhood is a maximal group of continuous houses that are painted with the same color.</p>

<ul>
	<li>For example: <code>houses = [1,2,2,3,3,2,1,1]</code> contains <code>5</code> neighborhoods <code>[{1}, {2,2}, {3,3}, {2}, {1,1}]</code>.</li>
</ul>

<p>Given an array <code>houses</code>, an <code>m x n</code> matrix <code>cost</code> and an integer <code>target</code> where:</p>

<ul>
	<li><code>houses[i]</code>: is the color of the house <code>i</code>, and <code>0</code> if the house is not painted yet.</li>
	<li><code>cost[i][j]</code>: is the cost of paint the house <code>i</code> with the color <code>j + 1</code>.</li>
</ul>

<p>Return <em>the minimum cost of painting all the remaining houses in such a way that there are exactly</em> <code>target</code> <em>neighborhoods</em>. If it is not possible, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
<strong>Output:</strong> 9
<strong>Explanation:</strong> Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
<strong>Output:</strong> 11
<strong>Explanation:</strong> Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
<strong>Output:</strong> -1
<strong>Explanation:</strong> Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == houses.length == cost.length</code></li>
	<li><code>n == cost[i].length</code></li>
	<li><code>1 &lt;= m &lt;= 100</code></li>
	<li><code>1 &lt;= n &lt;= 20</code></li>
	<li><code>1 &lt;= target &lt;= m</code></li>
	<li><code>0 &lt;= houses[i] &lt;= n</code></li>
	<li><code>1 &lt;= cost[i][j] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
  def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
    dp = [[[inf for _ in range(n)] for _ in range(target)], [[inf for _ in range(n)] for _ in range(target)]]
    previous = 0
    current = 1
    min_stats = [[[inf, inf, -1] for _ in range(target)], [[inf, inf, -1] for _ in range(target)]]
    if houses[0] == 0:
      for color in range(n):
        dp[previous][0][color] = cost[0][color]
    else:
      dp[previous][0][houses[0] - 1] = 0
    for color in range(n):
      if dp[previous][0][color] < min_stats[previous][0][0]:
        min_stats[previous][0][1] = min_stats[previous][0][0]
        min_stats[previous][0][0] = dp[previous][0][color]
        min_stats[previous][0][2] = color
      elif dp[previous][0][color] < min_stats[previous][0][1]:
        min_stats[previous][0][1] = dp[previous][0][color]
        
      
    for i_house in range(1, len(houses)):
      if houses[i_house] == 0:
        for group in range(min(target, i_house + 1)):
          for color in range(n):
            if group == 0:
              dp[current][group][color] = cost[i_house][color] + dp[previous][group][color]
            else:
              dp[current][group][color] = cost[i_house][color] + min(
                dp[previous][group][color], min_stats[previous][group - 1][1] if min_stats[previous][group - 1][2] == color else min_stats[previous][group - 1][0]
              )
      else:
        color = houses[i_house] - 1
        for group in range(min(target, i_house + 1)):
          if group == 0:
            dp[current][group][color] = dp[previous][group][color]
          else:
            dp[current][group][color] = min(
              dp[previous][group][color], min_stats[previous][group - 1][1] if min_stats[previous][group - 1][2] == color else min_stats[previous][group - 1][0]
            )

      for group in range(min(target, i_house + 1)):
        for color in range(n):
          if dp[current][group][color] < min_stats[current][group][0]:
            min_stats[current][group][1] = min_stats[current][group][0]
            min_stats[current][group][0] = dp[current][group][color]
            min_stats[current][group][2] = color
          elif dp[current][group][color] < min_stats[current][group][1]:
            min_stats[current][group][1] = dp[current][group][color]     
      
      previous ^= 1
      current ^= 1
      dp[current] = [[inf for _ in range(n)] for _ in range(target)]
      min_stats[current] = [[inf, inf, -1] for _ in range(target)]
    ret = min(dp[previous][target - 1])
    return -1 if ret == inf else ret
17188