1473. Paint House III (Dynamic Programming) 20.6.7 Hard

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 has 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 * n matrix cost and an integer target where:

houses[i]: is the color of the house i, 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 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 = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5
Example 4:

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


Solution no.1: my own BF backtracking O(n ^ m) T and O(m) S
class Solution(object):
    def minCost(self, houses, cost, m, n, target):
        """
        :type houses: List[int]
        :type cost: List[List[int]]
        :type m: int
        :type n: int
        :type target: int
        :rtype: int
        """
        self.cost = float('inf')
        self.dfs(houses, cost, m, n, target, -1, 0, 0, 0)
        return self.cost if self.cost != float('inf') else -1
    
    def dfs(self, houses, cost, m, n, target, prev_color, curr_index, curr_neigh, curr_cost):
        if curr_neigh == target and curr_index == m:
            self.cost = min(self.cost, curr_cost)
            return
        if curr_index == m or curr_neigh > target:
            return
        if houses[curr_index] != 0:
            if prev_color == houses[curr_index]:
                self.dfs(houses, cost, m, n, target, houses[curr_index], curr_index + 1, curr_neigh, curr_cost)
            else:
                self.dfs(houses, cost, m, n, target, houses[curr_index], curr_index + 1, curr_neigh + 1, curr_cost)
        else:
            for color in range(1, n + 1):
                if prev_color == color:
                    self.dfs(houses, cost, m, n, target, color, curr_index + 1, curr_neigh, curr_cost + cost[curr_index][color - 1])
                else:
                    self.dfs(houses, cost, m, n, target, color, curr_index + 1, curr_neigh + 1, curr_cost + cost[curr_index][color - 1])
                    

Solution no.2: memo
# the time complexity is m * t * n * n, we have m * t * n kinds of status( i.e. space complexity), 
# for each status, we should use a for loop to get the cost
class Solution(object):
    def minCost(self, houses, cost, m, n, target):
        """
        :type houses: List[int]
        :type cost: List[List[int]]
        :type m: int
        :type n: int
        :type target: int
        :rtype: int
        """
        memo = {}
        
        def helper(curr_index, curr_neigh, prev_color):
            key = (curr_index, curr_neigh, prev_color)
            if curr_index == m or curr_neigh > target:
                return 0 if curr_neigh == target else float('inf')
            if not key in memo:
                if houses[curr_index] == 0:
                    memo[key] = min(cost[curr_index][color - 1] + helper(curr_index + 1, curr_neigh + (color != prev_color), color) for color in range(1, n + 1))
                else:
                    memo[key] = helper(curr_index + 1, curr_neigh + (houses[curr_index] != prev_color), houses[curr_index])
            return memo[key]
            
        
        res = helper(0, 0, -1)
        return res if res != float('inf') else -1