<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 {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        // dp[i][j][target] = min(dp[i - 1][j][target] + cost[i][j],
        //                        dp[i - 1][not j][target - 1] + cost[i - 1][not j])
        // cout << "m=" << m << "  n=" << n << " target=" << target << endl;
        vector<vector<vector<long> > > dp(m, vector<vector<long> > (n, vector<long>(target + 1, -1)));
        if (houses[0] != 0) {
            int color = houses[0] - 1;
            dp[0][color][1] = 0;
        } else {
            for (int j = 0; j < n; j++) {
                dp[0][j][1] = cost[0][j];
            }
        }

        // for (int i = 0; i < n; i++) {
        //     cout << dp[0][i][1] << " " ;
        // }
        // cout << endl;
        for (int i = 1; i < m; i++) {
            if (houses[i] != 0) {
                int color = houses[i] - 1;
                for (int j = 0; j < n; j++) {
                    for (int t = 0; t < target; t++) {
                        if (color == j) {
                            if (dp[i - 1][j][t + 1] == -1) {
                                continue;
                            }
                            // cout << "same " << i << "  " << color << "   " << (t + 1) << endl;
                            if (dp[i][color][t + 1] == -1) {
                                dp[i][color][t + 1] = INT_MAX;
                            }
                            dp[i][color][t + 1] = min(dp[i][color][t + 1], dp[i - 1][j][t + 1]);
                            // dp[i][color][t + 1] = min(dp[i][color][t + 1], dp[i - 1][j][t + 1] + cost[i][color]);
                            // cout << dp[i - 1][j][t + 1] << "  " << cost[i][color] << "  " <<  dp[i][color][t + 1] << endl;
                        } else {
                            if (dp[i - 1][j][t] == -1) {
                                continue;
                            }
                            // cout << "not same " << i << "  " << color << "   " << (t + 1) << endl;
                            if (dp[i][color][t + 1] == -1) {
                                dp[i][color][t + 1] = INT_MAX;
                            }
                            // dp[i][color][t + 1] = min(dp[i][color][t + 1], dp[i - 1][j][t] + cost[i][color]);
                            dp[i][color][t + 1] = min(dp[i][color][t + 1], dp[i - 1][j][t]);
                            // cout << dp[i][color][t + 1] << endl;
                        }
                    }
                    // dp[i][color][t + 1] = min(dp[i - 1][color][t + 1], dp[i - 1][not color][t])
                }
            } else {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        for (int t = 0; t < target; t++) {
                            if (j == k) {
                                if (i != 0 && dp[i - 1][j][t + 1] == -1) {
                                    continue;
                                }
                                if (dp[i][j][t + 1] == -1) {
                                    dp[i][j][t + 1] = INT_MAX;
                                }
                                dp[i][j][t + 1] = min(dp[i][j][t + 1],  dp[i - 1][k][t + 1] + cost[i][j]);
                            } else {
                                if (i != 0 && dp[i - 1][k][t] == -1) {
                                    continue;
                                }
                                if (dp[i][j][t + 1] == -1) {
                                    dp[i][j][t + 1] = INT_MAX;
                                }
                                dp[i][j][t + 1] = min(dp[i][j][t + 1],  dp[i - 1][k][t] + cost[i][j]);
                            }
                        }

                    }
                }
            }
        }
        long res = INT_MAX;
        for (int i = 0; i < n; i++) {
            // cout << "res[" << i << "] is " << dp[m - 1][i][target] << endl;
            if (dp[m - 1][i][target] == -1) {
                continue;
            }
            res = min(res, dp[m - 1][i][target]);
        }
        if (res == INT_MAX) {
            return -1;
        }
        return res;
    }
};
23954