<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:
    // constraints: m <= 100 and cost[i][j] <= 10000 so total cost at most 1e6
    const int infty = 1e6+1;
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(target+1, vector<int>(n, infty)));
        for (int color = 1; color <= n; ++color) {
            if (houses[0] == 0)
                dp[0][1][color-1] = cost[0][color-1];
            else if (houses[0] == color)
                dp[0][1][color-1] = 0;
        }
        for (int house = 1; house < m; ++house) {
            for (int nbrhood = 1; nbrhood <= min(target, house+1); ++nbrhood) {
                // find cheapest two colors to color previous house
                int diff1 = 1; 
                int diff2 = 2;
                vector<int> prev = dp[house-1][nbrhood-1];
                if (prev[diff1-1] > prev[diff2-1]) {
                    diff1 = 2;
                    diff2 = 1;
                }
                for (int color = 3; color <= n; ++color) {
                    if (prev[color-1] < prev[diff1-1]) {
                        diff2 = diff1;
                        diff1 = color;
                    }
                    else if (prev[color-1] < prev[diff2-1])
                        diff2 = color;
                }
                for (int color = 1; color <= n; ++color) {
                    if (houses[house] && houses[house] != color)
                        continue;
                    int same_nbr_cost = dp[house-1][nbrhood][color-1];
                    int diff_nbr_cost = diff1 == color ? prev[diff2-1] : prev[diff1-1];
                    int curr_cost = houses[house] > 0 ? 0 : cost[house][color-1];
                    dp[house][nbrhood][color-1] = curr_cost + min(same_nbr_cost, diff_nbr_cost);
                }
            }
        }
        int res = *min_element(dp[m-1][target].begin(), dp[m-1][target].end());
        return res < infty ? res : -1;
    }
};
24699