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

# 1473. Paint House III

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

# A neighborhood is a maximal group of continuous houses that are painted with the same color.

# For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}].
# Given an array houses, an m x n matrix cost and an integer target where:

# houses[i]: is the color of the house i, and 0 if the house is not painted yet.
# cost[i][j]: is the cost of paint the house i with the color j + 1.
# Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.

# Example 1:
# Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
# Output: 9
# Explanation: 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.

# Example 2:
# Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
# Output: 11
# Explanation: 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.

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

# Constraints:
# m == houses.length == cost.length
# n == cost[i].length
# 1 <= m <= 100
# 1 <= n <= 20
# 1 <= target <= m
# 0 <= houses[i] <= n
# 1 <= cost[i][j] <= 10^4


class Solution:
    # I took 24 mins to successfully code this one
    # Thanks God!! I needed that!
    # it was necessary to run 4-5 debugging executions to grasp all the details of the
    # recurrence relation, my intuition was pretty good and I was in control at all times
    # the prev and target insights were identified since the beggining
    # there was an important detail: when house is already painted we don't include the cost
    # and I missed it and had to debug a few times, but I was quick to find the problem and fix it

    # n == possible indexes
    # m = possible colours
    # t = possible targets
    # runtime: O(n*m*t)
    # since colours == m
    # runtime: O(n*m^2*t), space: O(n*m*t)
    def minCost(
        self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
    ) -> int:

        r = self.dfs(0, -1, target, houses, cost, {})
        if r == math.inf:
            return -1
        return r

    def dfs(self, i, prev, target, houses, cost, memo):
        # print(i,prev,target)
        if i == len(houses):
            if target == 0:
                return 0
            return math.inf

        key = (i, prev, target)
        if key in memo:
            return memo[key]

        best = math.inf
        if houses[i] == 0:
            for j in range(len(cost[i])):  # we only do this if house is not painted yet
                colour_cost = cost[i][j]
                option_cost = math.inf
                if (
                    j + 1 == prev
                ):  # I had a nasty bug because colour (j) is indexed starting at 1, I missed it initially but was able to find it later
                    option_cost = self.dfs(i + 1, j + 1, target, houses, cost, memo)
                else:
                    option_cost = self.dfs(i + 1, j + 1, target - 1, houses, cost, memo)

                best = min(best, option_cost + colour_cost)
        else:  # house is already painted
            if prev == houses[i] and target >= 0:
                best = min(best, self.dfs(i + 1, houses[i], target, houses, cost, memo))
            elif prev != houses[i] and target > 0:
                best = min(
                    best, self.dfs(i + 1, houses[i], target - 1, houses, cost, memo)
                )

        memo[key] = best
        return memo[key]


# houses[i] == 0 if house is not painted, else is the colour of this house

# cost[i][j] is the cost of painting the house i with color j (1->n)

# we want to have target neighbourhoods
# which means we want to have target groups of houses painted with the same colour

# state

# we need to represent colour of previous house and if house is first
# if we decide to paint with same colour we should see if house is first
# if it is we increment target -= 1

# we can only paint a house from different colour than previous if target > 0
# we return math.inf

# recurrence relation:
# we must do a for loop in cost[i] every time to see the best option

# dp[i][prev][target] == MIN(cost[i][j] + dp[i][j][target-1] for all j) or target if j == prev

# break condition
# i == len(houses): return 0

26821