Problem Description

The "Paint House III" problem asks you to paint a row of m houses. Each house can be painted in one of n colors. Some houses may already be painted (indicated in the houses array, where houses[i] == 0 means unpainted, and any other value is the color). Painting an unpainted house with color j costs cost[i][j-1].

The goal is to paint all houses such that there are exactly target neighborhoods, where a neighborhood is a maximal group of consecutive houses painted with the same color. You must minimize the total painting cost. If it's impossible to form exactly target neighborhoods, return -1.

• Input:
  • houses: List of length m, each element is 0 (unpainted) or a color (1-indexed)
  • cost: m x n matrix, cost to paint house i with color j
  • m: Number of houses
  • n: Number of colors
  • target: Desired number of neighborhoods
• Constraints:
  • Each house must be painted exactly once
  • If a house is already painted, you cannot repaint it
  • Minimize the total painting cost
  • Return -1 if it's not possible to get exactly target neighborhoods

Thought Process

At first glance, this problem looks like a regular dynamic programming (DP) challenge, but the twist is the "neighborhood" constraint. For each house, you must decide what color to paint it and keep track of how painting choices affect the neighborhood count.

A brute-force approach would try all possible colorings for each house, and for each, count the neighborhoods, but this quickly becomes infeasible due to the exponential number of possibilities. We need to optimize by avoiding redundant work and reusing solutions to subproblems.

The key insight is to use DP with three state variables:

• The current house index
• The color of the previous house
• The number of neighborhoods formed so far

Solution Approach

We solve this problem using a top-down dynamic programming approach with memoization. The state is defined by:

• i: The current house index
• prev_color: The color of the previous house (to determine if a new neighborhood is formed)
• neigh: The number of neighborhoods formed so far

1. Base Cases:
   • If i == m (all houses considered): If neigh == target, return 0 (no more cost); else, return infinity (invalid state).
   • If neigh > target: Return infinity (too many neighborhoods).
2. Recursive Case:
   • If houses[i] is already painted, you must use that color. If it's different from prev_color, increment neigh by 1. Recurse to the next house.
   • If houses[i] == 0 (unpainted), try every color c (1 to n):
     • If c != prev_color, increment neigh by 1.
     • Add cost[i][c-1] to the total cost.
     • Take the minimum cost over all color choices.
3. Memoization:
   • Store results in a DP table (e.g., dp[i][prev_color][neigh]) to avoid recomputation.
4. Return:
   • If the answer is infinity, return -1; otherwise, return the minimum cost found.

Example Walkthrough

Suppose we have:

• houses = [0, 2, 1, 2, 0]
• cost = [[1,10],[10,1],[10,1],[1,10],[5,1]]
• m = 5
• n = 2
• target = 3

1. Start at house 0 (unpainted). Try color 1 (cost 1) and color 2 (cost 10).
2. For each choice, move to house 1 (already painted color 2). If the color is different from previous, increment neighborhoods.
3. Repeat for each house, keeping track of neighborhoods and total cost.
4. When reaching the end, check if neighborhoods == 3. If so, return the minimal cost found.
5. If no valid way, return -1.

This step-by-step process ensures all possibilities are considered but avoids redundant calculations by memoizing results.

Time and Space Complexity

Brute-force: Tries all colorings for every house, which is O(n^m) and not feasible for large m.

Optimized DP: There are up to m houses, n possible previous colors, and target possible neighborhoods. So the total number of DP states is O(m * n * target). For each state, we may try up to n colors, so total time is O(m * n^2 * target).

Space Complexity: The memoization table is O(m * n * target).

Summary

The "Paint House III" problem is a classic example of dynamic programming with multiple state variables. The key insight is to track the current house, the color of the previous house, and the number of neighborhoods formed so far. Memoization allows us to efficiently explore all valid painting options, ensuring we find the minimum cost or correctly report impossibility. This approach elegantly solves the challenge by reducing redundant work and managing complex state transitions.

Code Implementation

from functools import lru_cache

class Solution:
    def minCost(self, houses, cost, m, n, target):
        INF = float('inf')

        @lru_cache(None)
        def dp(i, prev_color, neigh):
            if neigh > target:
                return INF
            if i == m:
                return 0 if neigh == target else INF

            if houses[i]:
                new_neigh = neigh + (1 if houses[i] != prev_color else 0)
                return dp(i+1, houses[i], new_neigh)
            min_total = INF
            for color in range(1, n+1):
                new_neigh = neigh + (1 if color != prev_color else 0)
                total = cost[i][color-1] + dp(i+1, color, new_neigh)
                min_total = min(min_total, total)
            return min_total

        res = dp(0, 0, 0)
        return -1 if res == INF else res
      

#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

class Solution {
public:
    int m, n, target;
    int INF = 1000000000;
    int dp[101][21][101]; // m, n, target

    int dfs(vector<int>& houses, vector<vector<int>>& cost, int i, int prev_color, int neigh) {
        if (neigh > target) return INF;
        if (i == m) return neigh == target ? 0 : INF;
        if (dp[i][prev_color][neigh] != -1) return dp[i][prev_color][neigh];
        int ans = INF;
        if (houses[i] != 0) {
            int new_neigh = neigh + (houses[i] != prev_color ? 1 : 0);
            ans = dfs(houses, cost, i+1, houses[i], new_neigh);
        } else {
            for (int color = 1; color <= n; ++color) {
                int new_neigh = neigh + (color != prev_color ? 1 : 0);
                int total = cost[i][color-1] + dfs(houses, cost, i+1, color, new_neigh);
                ans = min(ans, total);
            }
        }
        return dp[i][prev_color][neigh] = ans;
    }

    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m_, int n_, int target_) {
        m = m_; n = n_; target = target_;
        memset(dp, -1, sizeof(dp));
        int res = dfs(houses, cost, 0, 0, 0);
        return res == INF ? -1 : res;
    }
};
      

import java.util.Arrays;

class Solution {
    int m, n, target;
    int INF = 1000000000;
    int[][][] memo;

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        this.m = m;
        this.n = n;
        this.target = target;
        memo = new int[m][n+1][target+1];
        for (int[][] arr2d : memo)
            for (int[] arr1d : arr2d)
                Arrays.fill(arr1d, -1);
        int res = dfs(houses, cost, 0, 0, 0);
        return res == INF ? -1 : res;
    }

    int dfs(int[] houses, int[][] cost, int i, int prevColor, int neigh) {
        if (neigh > target) return INF;
        if (i == m) return neigh == target ? 0 : INF;
        if (memo[i][prevColor][neigh] != -1) return memo[i][prevColor][neigh];
        int ans = INF;
        if (houses[i] != 0) {
            int newNeigh = neigh + (houses[i] != prevColor ? 1 : 0);
            ans = dfs(houses, cost, i+1, houses[i], newNeigh);
        } else {
            for (int color = 1; color <= n; ++color) {
                int newNeigh = neigh + (color != prevColor ? 1 : 0);
                int total = cost[i][color-1] + dfs(houses, cost, i+1, color, newNeigh);
                ans = Math.min(ans, total);
            }
        }
        memo[i][prevColor][neigh] = ans;
        return ans;
    }
}
      

var minCost = function(houses, cost, m, n, target) {
    const INF = 1e9+7;
    const memo = {};

    function dp(i, prevColor, neigh) {
        if (neigh > target) return INF;
        if (i === m) return neigh === target ? 0 : INF;
        const key = i + ',' + prevColor + ',' + neigh;
        if (memo.hasOwnProperty(key)) return memo[key];
        let ans = INF;
        if (houses[i] !== 0) {
            let newNeigh = neigh + (houses[i] !== prevColor ? 1 : 0);
            ans = dp(i+1, houses[i], newNeigh);
        } else {
            for (let color = 1; color <= n; ++color) {
                let newNeigh = neigh + (color !== prevColor ? 1 : 0);
                let total = cost[i][color-1] + dp(i+1, color, newNeigh);
                ans = Math.min(ans, total);
            }
        }
        memo[key] = ans;
        return ans;
    }

    const res = dp(0, 0, 0);
    return res === INF ? -1 : res;
};