# Paint House III
**Difficulty:** HARD
[External](https://leetcode.com/problems/paint-house-iii)
Canonical: https://scaleengineer.com/dsa/problems/paint-house-iii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
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`.

**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 = [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] <= 104`

# Approaches
## Top-Down Dynamic Programming (Recursion with Memoization)
This approach uses recursion with memoization, a top-down dynamic programming technique. We define a recursive function that explores all possible ways to paint the houses while keeping track of the current house index, the number of neighborhoods formed so far, and the color of the previous house. Memoization is used to store the results of subproblems to avoid redundant calculations, which is crucial for passing the time limits.
**Time:** O(m * target * n^2)
The number of states is `m * target * n`. For each state, if the house is not painted, we iterate through `n` colors, leading to the `n^2` factor. If all houses are painted, the complexity would be closer to `O(m * target * n)`. · **Space:** O(m * target * n)
This is for the memoization table `memo` of size `m x (target+1) x (n+1)`. The recursion depth adds an additional O(m) to the space complexity, which is dominated by the memoization table.
**Pros:** Relatively intuitive to formulate from the problem description.; It naturally prunes the search space by only exploring reachable states.
**Cons:** The time complexity of O(m * target * n^2) can be slow if n is large.; The space complexity of O(m * target * n) can be large.; Deep recursion could potentially lead to stack overflow for very large `m`, though not an issue with the given constraints.
### Explanation
The state of our recursive function can be defined as `solve(houseIndex, neighborhoodCount, prevColor)`. This function will return the minimum cost to paint houses from `houseIndex` to `m-1`, given that we have already formed `neighborhoodCount` neighborhoods in the prefix `0...houseIndex-1`, and the house at `houseIndex-1` was painted with `prevColor`.

When we are at `houseIndex`, we decide which color to paint it. 
- If `houses[houseIndex]` is not `0`, its color is fixed. We calculate the new neighborhood count. If the current house color is the same as `prevColor`, the count doesn't change. Otherwise, it increases by one. We then make a recursive call for `houseIndex + 1`.
- If `houses[houseIndex]` is `0`, we must try all `n` colors. For each color `c`, we calculate the cost (`cost[houseIndex][c-1]`) and the new neighborhood count, and make a recursive call. The minimum cost over all `n` choices is the result for the current state.

The base cases for the recursion are when we have processed all houses (`houseIndex == m`) or when the neighborhood count exceeds the `target`. A 3D memoization table `memo[m][target+1][n+1]` stores the results to prevent re-computation of the same state.

```java
class Solution {
    private int m, n, target;
    private int[] houses;
    private int[][] cost;
    private Integer[][][] memo;
    private final int MAX_COST = 1_000_001; // A value larger than max possible cost

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        this.houses = houses;
        this.cost = cost;
        this.m = m;
        this.n = n;
        this.target = target;
        // memo[houseIndex][neighborhoods][prevColor]
        this.memo = new Integer[m][target + 1][n + 1];

        int result = solve(0, 0, 0); // index, neighborhoods formed, prev_color

        return result >= MAX_COST ? -1 : result;
    }

    private int solve(int houseIndex, int neighborhoodCount, int prevColor) {
        if (neighborhoodCount > target) {
            return MAX_COST;
        }
        if (houseIndex == m) {
            return neighborhoodCount == target ? 0 : MAX_COST;
        }

        if (memo[houseIndex][neighborhoodCount][prevColor] != null) {
            return memo[houseIndex][neighborhoodCount][prevColor];
        }

        int minCost = MAX_COST;

        if (houses[houseIndex] != 0) { // House is already painted
            int currentColor = houses[houseIndex];
            int newNeighborhoodCount = neighborhoodCount + (currentColor == prevColor ? 0 : 1);
            minCost = solve(houseIndex + 1, newNeighborhoodCount, currentColor);
        } else { // House is not painted, try all colors
            for (int currentColor = 1; currentColor <= n; currentColor++) {
                int newNeighborhoodCount = neighborhoodCount + (currentColor == prevColor ? 0 : 1);
                int currentCost = cost[houseIndex][currentColor - 1] + solve(houseIndex + 1, newNeighborhoodCount, currentColor);
                minCost = Math.min(minCost, currentCost);
            }
        }

        return memo[houseIndex][neighborhoodCount][prevColor] = minCost;
    }
}
```
### Algorithm
- The core of this approach is a recursive function, let's call it `solve(houseIndex, neighborhoodCount, prevColor)`, which calculates the minimum cost.
- The parameters of this function are:
  - `houseIndex`: The index of the house we are currently considering to paint (from `0` to `m-1`).
  - `neighborhoodCount`: The number of neighborhoods formed so far, up to `houseIndex - 1`.
  - `prevColor`: The color of the previous house (`houseIndex - 1`). We can use `0` as a virtual color for the house before the first one.
- **Base Cases**:
  - If `neighborhoodCount` exceeds `target`, it's an invalid path, so we return a very large value (infinity).
  - If `houseIndex` reaches `m` (all houses considered), we check if `neighborhoodCount` is exactly `target`. If it is, we've found a valid painting scheme, and the cost for the remaining (none) houses is `0`. Otherwise, it's an invalid scheme, so we return infinity.
- **Recursive Step**:
  - If the current house `houses[houseIndex]` is already painted, we must use its color. We determine if this forms a new neighborhood by comparing its color to `prevColor` and recurse for the next house: `solve(houseIndex + 1, newNeighborhoodCount, houses[houseIndex])`.
  - If the house is not painted (`houses[houseIndex] == 0`), we try painting it with every possible color from `1` to `n`. For each color, we calculate the painting cost and the new neighborhood count, then recursively call the function for the next house. We take the minimum cost among all color choices.
- **Memoization**:
  - To avoid recomputing results for the same state `(houseIndex, neighborhoodCount, prevColor)`, we use a 3D array `memo` to store the results. Before computing, we check if the result is already in `memo`. After computing, we store the result in `memo`.

## Bottom-Up Dynamic Programming with Optimization
A more efficient solution uses bottom-up dynamic programming. The key idea is to build the solution iteratively, from the first house to the last. We can define a DP state `dp[i][k][p]` as the minimum cost to paint the first `i` houses, forming exactly `k` neighborhoods, with the `i`-th house painted in color `p`. The crucial observation is that the transition from house `i-1` to `i` involves an `O(n)` lookup, which can be optimized to `O(1)` by pre-calculating the two minimum costs from the previous state. Furthermore, we can optimize space because computing the DP values for house `i` only requires the values from house `i-1`.
**Time:** O(m * target * n)
We have an outer loop for `m` houses. Inside it, a loop for `target` neighborhoods. Inside that, we do two passes over `n` colors: one to find the two minimums and another to calculate the DP values. This gives `m * target * (O(n) + O(n)) = O(m * target * n)`. · **Space:** O(target * n)
We only need to store the DP table for the previous house to compute the table for the current house. Thus, we use two tables of size `(target+1) x (n+1)`, resulting in this space complexity.
**Pros:** Most efficient time complexity of O(m * target * n).; Optimal space complexity of O(target * n) due to space optimization.; Avoids recursion overhead and potential stack depth issues.
**Cons:** The logic, especially the state transitions and optimizations, can be more complex to reason about and implement correctly compared to the top-down approach.
### Explanation
This approach builds the solution from the ground up. We use a 2D DP array `dp[k][p]` to store the minimum cost for the current house, where `k` is the number of neighborhoods and `p` is the color of this house. We iterate through each house from `i = 1` to `m`.

For each house `i`, we calculate its `dp` table based on the `prev_dp` table (from house `i-1`). For each target neighborhood count `k` and each color `p`:

The cost to paint house `i-1` with color `p` is `paint_cost`. This is `cost[i-1][p-1]` if the house is unpainted, `0` if it's already painted with `p`, and infinity otherwise.

The total cost `dp[k][p]` is `paint_cost` plus the minimum cost from the previous state. This previous cost is derived from two possibilities:
1.  **Extending a neighborhood**: The previous house (`i-2`) was also painted with color `p`. The cost is inherited from `prev_dp[k][p]`. The number of neighborhoods remains `k`.
2.  **Starting a new neighborhood**: The previous house (`i-2`) had a different color. This means we had `k-1` neighborhoods up to house `i-2`. We need the minimum cost to achieve this, which is `min(prev_dp[k-1])`. 

To make the second case efficient, instead of re-calculating `min(prev_dp[k-1])` for each `p`, we pre-compute the two smallest values in the `prev_dp[k-1]` row. This reduces the transition from `O(n)` to `O(1)`, bringing the total time complexity down.

After iterating through all `m` houses, the minimum value in the `dp[target]` row is our answer. If this value is still infinity, no solution exists.

```java
class Solution {
    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        final int MAX_COST = 1_000_001;
        
        // dp[k][p] = min cost for houses processed so far, with k neighborhoods, last house color p
        int[][] dp = new int[target + 1][n + 1];
        for (int[] row : dp) {
            java.util.Arrays.fill(row, MAX_COST);
        }
        
        // Base case: before painting any house (i=0), 0 cost for 0 neighborhoods.
        // Any "previous color" is valid for this virtual state.
        for (int p = 0; p <= n; p++) {
            dp[0][p] = 0;
        }

        for (int i = 1; i <= m; i++) {
            int houseIdx = i - 1;
            int[][] next_dp = new int[target + 1][n + 1];
            for (int[] row : next_dp) {
                java.util.Arrays.fill(row, MAX_COST);
            }

            for (int k = 1; k <= target && k <= i; k++) {
                // Find the two cheapest colors for the previous state with k-1 neighborhoods
                int min1 = MAX_COST, color1 = -1;
                int min2 = MAX_COST;
                for (int p_prev = 1; p_prev <= n; p_prev++) {
                    if (dp[k - 1][p_prev] < min1) {
                        min2 = min1;
                        min1 = dp[k - 1][p_prev];
                        color1 = p_prev;
                    } else if (dp[k - 1][p_prev] < min2) {
                        min2 = dp[k - 1][p_prev];
                    }
                }

                for (int p = 1; p <= n; p++) {
                    if (houses[houseIdx] != 0 && houses[houseIdx] != p) {
                        continue;
                    }

                    int paintCost = (houses[houseIdx] == 0) ? cost[houseIdx][p - 1] : 0;
                    
                    // Case 1: Extend the current neighborhood
                    int cost1 = dp[k][p];

                    // Case 2: Start a new neighborhood
                    int cost2 = (p == color1) ? min2 : min1;
                    
                    int totalCost = paintCost + Math.min(cost1, cost2);
                    if (totalCost < MAX_COST) {
                        next_dp[k][p] = totalCost;
                    }
                }
            }
            dp = next_dp;
        }

        int result = MAX_COST;
        for (int p = 1; p <= n; p++) {
            result = Math.min(result, dp[target][p]);
        }

        return result >= MAX_COST ? -1 : result;
    }
}
```
### Algorithm
- Define a DP table `dp[k][p]` which stores the minimum cost to paint the houses up to the current one (say, `i-1`), forming `k` neighborhoods, with the last house `i-1` painted in color `p`.
- Since the calculation for house `i` only depends on the results for house `i-1`, we can optimize space by using only two 2D arrays: `dp` for the current house `i` and `prev_dp` for the previous house `i-1`.
- **Initialization**: Before processing any houses (a virtual state at `i=0`), the cost is `0` to have `0` neighborhoods. So, `prev_dp[0][any_color] = 0`, and all other entries are infinity.
- **Iteration**: We iterate through each house `i` from `1` to `m`.
  - For each house, we compute the new `dp` table.
  - We iterate through the number of neighborhoods `k` from `1` to `target`.
  - To optimize the transition, for each `k`, we first find the two minimum costs from the previous state with `k-1` neighborhoods (`prev_dp[k-1]`). Let these be `min1` (with color `color1`) and `min2`. This takes O(n) time.
  - Then, we iterate through each possible color `p` for the current house `i-1`.
  - The cost to paint the current house with color `p` is `paint_cost`.
  - The total cost is `paint_cost` plus the minimum cost from the previous house. This previous cost is the minimum of two cases:
    1.  The previous house had the same color `p`: `prev_dp[k][p]`.
    2.  The previous house had a different color (forming a new neighborhood): This requires finding the minimum of `prev_dp[k-1]` over all colors except `p`. This is where our pre-calculated `min1` and `min2` come in handy. The cost is `min1` if `p` is not `color1`, otherwise it's `min2`.
  - We update `dp[k][p]` with this minimum total cost.
- After iterating through all houses, the answer is the minimum value in `dp[target]` across all colors.

# Solutions
### Java

```java
class Solution {
public
  int minCost(int[] houses, int[][] cost, int m, int n, int target) {
    int[][][] f = new int[m][n + 1][target + 1];
    final int inf = 1 << 30;
    for (int[][] g : f) {
      for (int[] e : g) {
        Arrays.fill(e, inf);
      }
    }
    if (houses[0] == 0) {
      for (int j = 1; j <= n; ++j) {
        f[0][j][1] = cost[0][j - 1];
      }
    } else {
      f[0][houses[0]][1] = 0;
    }
    for (int i = 1; i < m; ++i) {
      if (houses[i] == 0) {
        for (int j = 1; j <= n; ++j) {
          for (int k = 1; k <= Math.min(target, i + 1); ++k) {
            for (int j0 = 1; j0 <= n; ++j0) {
              if (j == j0) {
                f[i][j][k] =
                    Math.min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);
              } else {
                f[i][j][k] =
                    Math.min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);
              }
            }
          }
        }
      } else {
        int j = houses[i];
        for (int k = 1; k <= Math.min(target, i + 1); ++k) {
          for (int j0 = 1; j0 <= n; ++j0) {
            if (j == j0) {
              f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k]);
            } else {
              f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1]);
            }
          }
        }
      }
    }
    int ans = inf;
    for (int j = 1; j <= n; ++j) {
      ans = Math.min(ans, f[m - 1][j][target]);
    }
    return ans >= inf ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCost(vector<int> &houses, vector<vector<int>> &cost, int m, int n,
              int target) {
    int f[m][n + 1][target + 1];
    memset(f, 0x3f, sizeof(f));
    if (houses[0] == 0) {
      for (int j = 1; j <= n; ++j) {
        f[0][j][1] = cost[0][j - 1];
      }
    } else {
      f[0][houses[0]][1] = 0;
    }
    for (int i = 1; i < m; ++i) {
      if (houses[i] == 0) {
        for (int j = 1; j <= n; ++j) {
          for (int k = 1; k <= min(target, i + 1); ++k) {
            for (int j0 = 1; j0 <= n; ++j0) {
              if (j == j0) {
                f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);
              } else {
                f[i][j][k] =
                    min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);
              }
            }
          }
        }
      } else {
        int j = houses[i];
        for (int k = 1; k <= min(target, i + 1); ++k) {
          for (int j0 = 1; j0 <= n; ++j0) {
            if (j == j0) {
              f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]);
            } else {
              f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]);
            }
          }
        }
      }
    }
    int ans = 0x3f3f3f3f;
    for (int j = 1; j <= n; ++j) {
      ans = min(ans, f[m - 1][j][target]);
    }
    return ans == 0x3f3f3f3f ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int: f = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)] if houses[0] == 0: for j, c in enumerate(cost[0], 1): f[0][j][1] = c else: f[0][houses[0]][1] = 0 for i in range(1, m): if houses[i] == 0: for j in range(1, n + 1): for k in range(1, min(target + 1, i + 2)): for j0 in range(1, n + 1): if j == j0: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]) else: f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]) else: j = houses[i] for k in range(1, min(target + 1, i + 2)): for j0 in range(1, n + 1): if j == j0: f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]) else: f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]) ans = min(f[- 1][j][target] for j in range(1, n + 1)) return - 1 if ans >= inf else ans

```