<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 {
    int INF = 1e9+7;
public:
    int recur_2(vector<int>& houses, vector<vector<int>>& cost, int target, int ind, int lastColor, int curTarget,vector<vector<vector<int>>>& dp) {
        if (curTarget > target) return INF;
        if (ind >= houses.size()) {
            if (curTarget == target) return 0;
            else return INF;
        }
        if (dp[ind][lastColor][curTarget] != -1) return dp[ind][lastColor][curTarget];
        if (houses[ind] != 0) {
            return dp[ind][lastColor][curTarget] = recur_2(houses, cost, target, ind+1, houses[ind], (lastColor == houses[ind]) ? curTarget : curTarget + 1, dp);
        }
        int ans = INF;
        for (int i = 0; i < cost[ind].size(); i++) {
            ans = min(ans, recur_2(houses, cost, target,ind+1,i+1, (lastColor == i+1) ? curTarget : curTarget + 1, dp) + cost[ind][i]);
        }
        return dp[ind][lastColor][curTarget] = ans;
    }
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        int ans = INF;
        vector<vector<vector<int>>>dp(m+1, vector<vector<int>>(n+1, vector<int>(target+1, -1)));
        ans = recur_2(houses, cost, target, 0, 0, 0, dp);
        return ans >= INF ? -1 : ans;
    }
};

// //1 0 0 2 3 -> 5
// // 1 0 2 

// class Solution {
//     vector<int> H;
//     vector<vector<int>> C;
//     int M, N, T, INF = 1e9 + 7;
//     vector<vector<vector<int>>> memo;
//     int dp(int i, int last, int cnt) {
//         if (cnt > T) return INF;
//         if (i == M) return cnt == T ? 0 : INF;
//         if (memo[i][last][cnt] != -1) return memo[i][last][cnt];
//         if (H[i]) return memo[i][last][cnt] = dp(i + 1, H[i], H[i] == last ? cnt : (cnt + 1));
//         int ans = INF;
//         for (int j = 0; j < N; ++j) ans = min(ans, C[i][j] + dp(i + 1, j + 1, j + 1 == last ? cnt : (cnt + 1)));
//         return memo[i][last][cnt] = ans;
//     }
// public:
//     int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
//         H = houses, C = cost, M = m, N = n, T = target;
//         memo.assign(M, vector<vector<int>>(N + 1, vector<int>(T + 1, -1)));
//         int ans = dp(0, 0, 0);
//         return ans == INF ? -1 : ans;
//     }
// 	// If you find helpful than upvote
// };
18553