<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:

        memo = [[[-1] * 21 for _ in range(100)] for _ in range(100)]
        MAX_COST = 1000001 

        def findMinCost(houses, cost, target_count, curr_index, neighborhood_count, prev_coler):

            if curr_index == len(houses):
                return 0 if neighborhood_count == target_count else MAX_COST
               
            if neighborhood_count > target_count:
                return MAX_COST
        
            if memo[curr_index][neighborhood_count][prev_coler] != -1:
                return memo[curr_index][neighborhood_count][prev_coler]
                
            min_cost = MAX_COST
            if houses[curr_index] != 0:
                new_neighborhood_count = neighborhood_count  + (houses[curr_index] != prev_coler)
                min_cost = findMinCost(houses, cost, target, curr_index+1, new_neighborhood_count, houses[curr_index])
            else:
                total_colors = len(cost[0])
                for color in range(1, total_colors+1):
                    new_neighborhood_count = neighborhood_count  + (color != prev_coler)
                    curr_cost = cost[curr_index][color-1] + findMinCost(houses, cost, target, curr_index+1, new_neighborhood_count, color)
                    min_cost = min(min_cost, curr_cost)
                    
            memo[curr_index][neighborhood_count][prev_coler] = min_cost
            return min_cost
            
        answer = findMinCost(houses, cost, target, 0, 0, 0)
        return -1 if answer == MAX_COST else answer

        '''
        #dp : houses
        #dp[] : colerは 1-nなので、0-nの配列を作る
        dp_cost  = [[float('inf')] * (n+1) for _ in range(m)] #その色で塗った時のコスト
        dp_group = [[float('inf')] * (target+1) for _ in range(m)] #neighborを考慮したコスト

        #ininialze house[0]
        if houses[0] != 0:
            dp_cost[0][house] = 0  # already painted, cost is 0
        else:
            for color in range(1, n+1):
                dp_cost[0][color] = cost[0][color-1]

        for color in range(1, n+1):
            dp_group[0][color] = 1

        for i in range(1, m):
            # House is already painted
            if houses[i] != 0:
                current_color = houses[i]
                for prev_color in range(1, n+1):
                    dp_cost[i][current_color] = dp_cost[i-1][prev_color]
                    if current_color != prev_color:
                        dp_group[i][current_color] = dp_group[i-1][prev_color] + 1
                    else:
                        dp_group[i][current_color] = dp_group[i-1][prev_color]


            else:
                for current_color in range(1, n+1):
                    for prev_color in range(1, n+1):




            answer += min(dp[i])

        return answer
        '''

        '''
        dp = [[[float('inf') for _ in range(n)] for _ in range(target)] for _ in range(m)]

        if houses[0] != 0:
            dp[0][0][houses[0]-1] = 0
        else:
            for color in range(n):
                dp[0][0][color] = cost[0][color]

        for house in range(1, m):
            for neighbor in range(target):
                for color in range(n):
                    if houses[house] != 0:
                        if houses[house]-1 == color:
                            if dp[house-1][neighbor][color] != float('inf'):
                                dp[house][neighbor][color] = min(dp[house][neighbor][color], dp[house-1][neighbor][color])
                        else:
                            if neighbor < (target-1):
                                tmp = dp[house-1][neighbor][houses[house]-1]
                                dp[house-1][neighbor][houses[house]-1] = float('inf')
                                dp[house][neighbor+1][houses[house]-1] = min(dp[house][neighbor+1][houses[house]-1], min(dp[house-1][neighbor]))
                                dp[house-1][neighbor][houses[house]-1] = tmp
                    else:
                        min_index = dp[house-1][neighbor].index(min(dp[house-1][neighbor]))
                        if color == min_index:
                            dp[house][neighbor][color] = min(dp[house][neighbor][color], dp[house-1][neighbor][color] + cost[house][color])
                        else:
                            if neighbor < (target-1):
                                tmp = dp[house-1][neighbor][color]
                                dp[house-1][neighbor][color] = float('inf')
                                dp[house][neighbor+1][color] = min(dp[house][neighbor+1][color], min(dp[house-1][neighbor]) + cost[house][color])
                                dp[house-1][neighbor][color] = tmp

        print(dp)
        answer = min(dp[-1][target-1])
        return -1 if answer == float('inf') else answer
        '''

32785