<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:
#Top Down DP
        # memo = {}
        # def dp(i,t,prev):
        #     if (i,t,prev) in memo: return memo[(i,t,prev)]
        #     if i == m:
        #         return 0 if t == target else float('inf')
        #     if houses[i] == 0:
        #         temp = float('inf')
        #         for color in range(1,n+1):
        #             if prev != color:
        #                 temp = min(temp, cost[i][color-1] + dp(i+1,t+1,color))
        #             else:
        #                 temp = min(temp, cost[i][color-1] + dp(i+1,t,color))
        #         memo[(i,t,prev)] = temp
        #     else:
        #         if prev != houses[i]:
        #             memo[(i,t,prev)] = dp(i+1, t+1, houses[i])
        #         else:
        #             memo[(i,t,prev)] = dp(i+1, t, houses[i])
        #     return memo[(i,t,prev)]

        # res = dp(0,0,0)
        # return  res if res != float('inf') else -1
        #Time:O(m*n*target) Space:O(m*n*target)


#Bottom Up DP
        # dp = [[[float('inf')] * (n+1) for _ in range(target+1)] for _ in range(m+1)]
        # for c in range(1, n + 1):
        #     if houses[0] == 0:
        #         # First house can be painted with any color if houses[i]==0
        #         dp[0][1][c] = cost[0][c - 1]     
        #     else:
        #         dp[0][1][houses[0]] = 0
        # for i in range(1,m):
        #     for t in range(1,target+1):
        #         for c in range(1,n+1):
        #             if houses[i] == 0:
        #                  for prev_color in range(1, n + 1):  # Check previous colors
        #                     if prev_color == c:
        #                         dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t][prev_color] + cost[i][c - 1])
        #                     else:
        #                         if t > 1:
        #                             dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t - 1][prev_color] + cost[i][c - 1])

        #             else:
        #                 for prev_color in range(1, n + 1):
        #                     if prev_color == c:
        #                         dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t][prev_color])
        #                     else:
        #                         if t > 1:
        #                             dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t - 1][prev_color])

        # res = min(dp[m-1][target])
        # return res if res != float('inf') else -1
        MAX_COST = float('inf')
        
        # DP table: dp[i][t][c] represents the min cost to paint houses 0..i with t neighborhoods and house i painted with color c
        dp = [[[MAX_COST] * (n + 1) for _ in range(target + 1)] for _ in range(m + 1)]
        
        # Base case: no house painted, so 0 cost
        for c in range(1, n + 1):
            if houses[0] == 0:
                dp[0][1][c] = cost[0][c - 1]  # First house can be painted with any color
            else:
                dp[0][1][houses[0]] = 0  # First house already painted
        
        # Fill the DP table
        for i in range(1, m):  # For each house
            for t in range(1, target + 1):  # For each neighborhood count
                for c in range(1, n + 1):  # For each possible color for house i
                    if houses[i] == 0:  # If the house is not painted
                        # Try to paint the house with color c
                        for prev_color in range(1, n + 1):  # Check previous colors
                            if prev_color == c:
                                dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t][prev_color] + cost[i][c - 1])
                            else:
                                dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t - 1][prev_color] + cost[i][c - 1])
                    else:  # If the house is already painted
                        if houses[i] == c:
                            for prev_color in range(1, n + 1):
                                if prev_color == c:
                                    dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t][prev_color])
                                else:
                                    dp[i][t][c] = min(dp[i][t][c], dp[i - 1][t - 1][prev_color])
        
        # The answer is the minimum cost to paint all houses with exactly target neighborhoods
        res = min(dp[m - 1][target][c] for c in range(1, n + 1))
        return res if res != MAX_COST else -1
    #Time:O(m*n*target) Space:O(m*n*target)
        
21316