1473. Paint House III

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.

class Solution {
    int dp[101][23][101];
    int helper(vector<int>& h, vector<vector<int>>& c, int t, int cur, int p) {
        if(t < 0) return 987654321;
        if(cur == h.size()) {
            return t ? 987654321 : 0;
        }
        if(dp[cur][p][t] != -1) return dp[cur][p][t];
        int& res = dp[cur][p][t] = INT_MAX;
        if(h[cur] == 0) {
            for(int i = 0; i < c[cur].size(); i++) {
                res = min(res, helper(h, c, t - (p != (i+1)), cur + 1, i+1) + c[cur][i]);
            }
        } else {
            res = helper(h,c, t - (h[cur] != p), cur + 1, h[cur]);
        }
        return res;
    }
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        memset(dp,-1,sizeof(dp));
        int res = helper(houses, cost, target, 0, 22);
        if(res >= 987654321) return -1;
        return res;
    }
};