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

'''
Brute Force - For every non-painted house, try every single paint and then return the minimum cost if if the array fits into the target - O(len(costs)^houses)

Notes
- We can check if the house fits into target in O(n) time
- Feels like a dynamic programming problem
- This idea of "grouping" houses together
    - What if I start at house i, move back and paint all the houses that are 0 to the same color as house i, then my result is simply I created a group + target - 1?
    - What is my solution at index i, if my target was 1,2,3,4,...,target
    
Pseudocode
- dp[i][j] - represent minimum cost to paint the ith index some color, with j target, considering elements from 0 to the ith house
- For each house
    - For each target
        - For each paint
            - If the house is not yet colored or is colored but is of the paint
                - dp[i][j] = min(dp[i][j], cur_cost + dp[k][j - 1]) where k = 0 - i - 1 inclusive

I may need to separate it out by colors as well because you don't know when you do the j - 1 here if the kth house was painted the j - 1th color as well then it's all going to be continuous...

- It's clear to me houses and cur_target are the outer loops, because you need to consider the cur_target - 1 to derive cur_target
- Separate the dp by the color, which just means my dp changes
- dp[i][j][k] = min(dp[i][j][k], cost + dp[i - 1][j][k], cost + dp[i - 1][j - 1][b])
    - dp[i - 1][j][k] -> if i were to color this as the same color with the house before me, then my target stays the same
    - dp[i - 1][j - 1][b] -> if I were to color this as a different color than the house before me, then my target is reduced by 1, but I need to consider all paints that are not my current paint. Don't need to do a -> 0 to i - 1 here because I'm trying to extend the group but really I already solved this problem before in previous loops with my first condition with different paints, this case is only if it's a different paint
    
- i represents current house
- j represents current target
- k represents my current paint

Adding infinity here...
'''

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        dp = [[[float('inf') for _ in range(n)] for _ in range(target + 1)] for _ in range(len(houses))]
        
        # Why this is a problem 
        # It's because this is for when cur_target == 1, but think about it, then you need to use the same color throughout which is accounted for in dp[i - 1][cur_target][cur_paint], you can't use the other paint's but 0th target...you're forced to use the same paint
#         for i in range(n):
#             dp[0][0][i] = 0
            
        for i in range(n):
            if houses[0] == i + 1:
                dp[0][1][i] = 0
            elif houses[0] == 0:
                dp[0][1][i] = cost[0][i]
            
            
        for i in range(1, len(houses)):
            for cur_target in range(1, target + 1):
                for cur_paint in range(n):
                    cur_cost = 0
                    if houses[i] == 0:
                        cur_cost += cost[i][cur_paint]
                    elif houses[i] != cur_paint + 1:
                        continue
                    
                    dp[i][cur_target][cur_paint] = cur_cost + dp[i - 1][cur_target][cur_paint]
                    
                    for other_paint in range(n):
                        if other_paint != cur_paint:
                            dp[i][cur_target][cur_paint] = min(dp[i][cur_target][cur_paint], cur_cost + dp[i - 1][cur_target - 1][other_paint])
                            
        # row is the target, col is the paint
    
        min_cost = float('inf')
        
        for i in range(n):
            min_cost = min(min_cost, dp[-1][-1][i])
        
        return min_cost if min_cost != float('inf') else -1
        

25445