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.

&nbsp;
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.


&nbsp;
Constraints:


	m == houses.length == cost.length
	n == cost[i].length
	1 &lt;= m &lt;= 100
	1 &lt;= n &lt;= 20
	1 &lt;= target &lt;= m
	0 &lt;= houses[i] &lt;= n
	1 &lt;= cost[i][j] &lt;= 104


class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        @cache
        def dp(i, p, h):
            if (h > target) or (i == m and h != target):
                return inf
            if i == m:
                return 0
            if houses[i] != 0:
                return dp(i + 1, houses[i], h + int(p != houses[i]))

            best = inf
            for j, c in enumerate(cost[i], 1):
                best = min(best, dp(i + 1, j, h + int(p != j)) + c)
            return best

        res = dp(0, 0, 0)
        return res if res != inf else -1
class Solution {
    public int helper(int idx, int[] houses, int[][] cost,int target, int prevColor,int neigh,Integer[][][] dp)
    {
        if(idx==houses.length || neigh>target)
        {
            if(neigh==target)
                return 0;
            return Integer.MAX_VALUE;
        }
        if(dp[idx][prevColor][neigh]!=null)
            return dp[idx][prevColor][neigh];
        int minCost = Integer.MAX_VALUE;

        if(houses[idx]==0)
        {
            for(int j = 0;j<cost[idx].length;j++)
            {
                int minCostHere = Integer.MAX_VALUE;

                if(j+1==prevColor) // Painting the house with the same colour as that of the previous one.
                    minCostHere = helper(idx+1,houses,cost,target,prevColor,neigh,dp);

                else // Painting the house with a different color and incrementing the neighbour count.
                    minCostHere = helper(idx+1,houses,cost,target,j+1,neigh+1,dp);

                if(minCostHere!=Integer.MAX_VALUE)
                    minCostHere+=cost[idx][j];

                minCost = Math.min(minCostHere,minCost);
            }
        }
        else
        {
            if(houses[idx]==prevColor)
                minCost = helper(idx+1,houses,cost,target,prevColor,neigh,dp);
            else
                minCost = helper(idx+1,houses,cost,target,houses[idx],neigh+1,dp);
        }

        return dp[idx][prevColor][neigh] = minCost;

    }
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {

        Integer[][][] dp = new Integer[m][n+1][target+1];
        int ans = helper(0,houses,cost,target,0,0,dp);
        return ans==Integer.MAX_VALUE?-1:ans;
    }
}
class Solution {
    int dp[101][22][101];
    vector<int> h;//m
    vector<vector<int>> c;//n
    int mm; int nn; int t;
    int dfs(int idx, int prev, int curt){
        if(curt<1)
            return INT_MAX;
        if(idx==mm)
            return (curt==1)?0:INT_MAX;
        if(dp[idx][prev][curt]!=-1)
            return dp[idx][prev][curt];
        int res=INT_MAX;
        int color=h[idx];
        if(color==0){
            for(int x=0;x<nn;x++){
                color=x+1;
                int rres=dfs(idx+1,color,curt-(prev!=21 and prev!=color));
                if(rres!=INT_MAX)
                    res=min(c[idx][color-1]+rres,res);
            }
        }else{
            return dp[idx][prev][curt]=dfs(idx+1,color,curt-(prev!=21 and prev!=color));
        }
        return dp[idx][prev][curt]=res;
    }
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        h=houses,c=cost,mm=m,nn=n,t=target;
        memset(dp,-1,sizeof(dp));
        int res=dfs(0,21,t);
        return res==INT_MAX?-1:res;
    }
};
var minCost = function(houses, cost, m, n, target) {
    let map = new Map();

    function dfs(idx = 0, prevColor = -1, neighborhoods = 0) {
        if (idx === m) return neighborhoods === target ? 0 : Infinity;

        let key = `${idx}-${prevColor}-${neighborhoods}`;
        if (map.has(key)) return map.get(key);
        
        let color = houses[idx];
        // If the current house is already painted
        if (color > 0) {
            return color !== prevColor ? dfs(idx + 1, color, neighborhoods + 1) : dfs(idx + 1, color, neighborhoods);
        }

        let minCost = Infinity;
        for (let i = 1; i <= n; i++) {
            let potentialCost;
            // If color i is !== prevColor, increment the neighborhood count
            if (i !== prevColor) potentialCost = dfs(idx + 1, i, neighborhoods + 1);
            // Otherwise, the neighborhood simply expanded so the neighborhood count stays the same
            else potentialCost = dfs(idx + 1, i, neighborhoods);
            
            if (potentialCost === Infinity) continue;
            minCost = Math.min(minCost, cost[idx][i - 1] + potentialCost);
        }
        map.set(key, minCost);
        return minCost;
    }
    
    let minCost = dfs();
    return minCost === Infinity ? -1 : minCost;
};
Paint House III