Formatted question description: https://leetcode.ca/all/1473.html

1473. Paint House III (Hard)

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 has 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 * n matrix cost and an integer target where:

  • houses[i]: is the color of the house i, 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 not possible return -1.

 

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 = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:

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.

 

Constraints:

  • m == houses.length == cost.length
  • n == cost[i].length
  • 1 <= m <= 100
  • 1 <= n <= 20
  • 1 <= target <= m
  • 0 <= houses[i] <= n
  • 1 <= cost[i][j] <= 10^4

Related Topics:
Dynamic Programming

Solution 1. DP Top-down

This looks like a DP problem because:

  1. it involves searching
  2. it only cares about the optimal solution – Optimal substructure
  3. During searching, we might go into the same state from different paths – Overlapping sub-problems.

The first task we need to do is to design the state of the sub-problem. I identified three:

  • the index of the current house (we scan them one by one from left to right). Denote it as i, 0 <= i < M.
  • The color of the previous house. Denote it as last, 0 <= last <= N.
  • Lastly, the count of the neighbors. Denote it as cnt, 0 <= cnt <= target + 1.

So we can represent the state using dp[i][last][cnt]

Now we need to think about the transition between the states. It’s quite straight forward:

  • If house[i] is already painted, we just skip it so dp[i][last][cnt] = dp[i + 1][H[i]][H[i] == last ? cnt : (cnt + 1)].
  • Otherwise, we just try colors from 1 to N, and store the best option in dp[i][last][cnt].
dp[i][last][cnt] = dp[i + 1][H[i]][H[i] == last ? cnt : (cnt + 1)]                                     // If house[i] > 0
                 = min( cost[i][j] + dp[i + 1][j + 1][j + 1 == last ? cnt : (cnt + 1)] | 0 <= j < N )  // If house[i] == 0

We initialize dp array using -1 which means unvisited.

For invalid states, like cnt > T or i == M && cnt != T, we mark the corresponding dp value as Infinity.

The answer is dp[0][0][0].

// OJ: https://leetcode.com/problems/paint-house-iii/

// Time: O(N^2 * MT)
// Space: O(MNT)
class Solution {
    vector<int> H;
    vector<vector<int>> C;
    int M, N, T, INF = 1e6;
    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;
    }
};

Solution 2. Bottom-up DP

Let dp[i][last][cnt] be the answer to the sub-problem on the houses in range [i, M) and last is the color of the i - 1-th house, and cnt is the number of neighbors existed before i - 1-th house. 0 <= i < M, 1 <= last <= N, 0 <= cnt <= M.

For dp[i][last][cnt], we have the following options:

  • If houses[i] > 0, dp[i][last][cnt] = dp[i + 1][houses[i]][ houses[i] == last ? cnt : (cnt + 1) ].
  • Otherwise, we try different colors for the i-th house, dp[i][last][cnt] = min( dp[i + 1][j][ j == last ? cnt : (cnt + 1) ] + cost[i][j - 1] | 1 <= j <= N ).
dp[i][last][cnt] = dp[i + 1][houses[i]][ houses[i] == last ? cnt : (cnt + 1) ]         // If houses[i] > 0
                 = min( dp[i + 1][j][ j == last ? cnt : (cnt + 1) ] + cost[i][j - 1] | 1 <= j <= N )    // If houses[i] == 0
dp[M][last][target] = 0  where 0 < last <= N

The dp array are initialized with value Infinity.

// OJ: https://leetcode.com/problems/paint-house-iii/

// Time: O(N^2 * MT)
// Space: O(MNT)
class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        int INF = 1e6;
        vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(target + 2, INF)));
        for (int last = 0; last <= n; ++last) dp[m][last][target] = 0;
        for (int i = m - 1; i >= 0; --i) {
            for (int last = 0; last <= n; ++last) {
                for (int cnt = 0; cnt <= target; ++cnt) {
                    if (houses[i]) dp[i][last][cnt] = dp[i + 1][houses[i]][houses[i] == last ? cnt : (cnt + 1)];
                    else {
                        for (int j = 1; j <= n; ++j) dp[i][last][cnt] = min(dp[i][last][cnt], dp[i + 1][j][j == last ? cnt : (cnt + 1)] + cost[i][j - 1]);
                    }
                }
            }
        }
        return dp[0][0][0] == INF ? -1 : dp[0][0][0];
    }
};

Java

class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        final int INFINITY = 1000000000;
        int[][][] dp = new int[m + 1][target + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= target; j++) {
                for (int k = 0; k <= n; k++)
                    dp[i][j][k] = INFINITY;
            }
        }
        if (houses[0] > 0)
            dp[0][1][houses[0]] = 0;
        else {
            for (int i = 1; i <= n; i++)
                dp[0][1][i] = cost[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= target; j++) {
                if (houses[i] > 0) {
                    int temp = houses[i];
                    for (int k = 1; k <= n; k++) {
                        if (temp == k)
                            dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j][k]);
                        else
                            dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j - 1][k]);
                    }
                } else {
                    for (int k = 1; k <= n; k++) {
                        for (int s = 1; s <= n; s++) {
                            if (k == s)
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][s] + cost[i][k - 1]);
                            else
                                dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][s] + cost[i][k - 1]);
                        }
                    }
                }
            }
        }
        int minCost = INFINITY;
        for (int i = 1; i <= n; i++)
            minCost = Math.min(minCost, dp[m - 1][target][i]);
        return minCost == INFINITY ? -1 : minCost;
    }
}

All Problems

All Solutions