Problem Description

The "Paint House" problem is a classic dynamic programming challenge. Given a row of n houses, each house can be painted with one of three colors: red, blue, or green. The cost of painting each house with a certain color is provided in a costs matrix, where costs[i][j] represents the cost of painting house i with color j (j=0 for red, j=1 for blue, j=2 for green).

The constraint is that no two adjacent houses can be painted with the same color. The goal is to determine the minimum total cost to paint all houses under this constraint.

• There is always at least one valid way to paint the houses.
• You cannot reuse the same color for two consecutive houses.
• The input costs is a non-empty list of lists, where each inner list has exactly three elements.

Thought Process

At first glance, a brute-force solution would try all possible colorings for each house, checking the constraint at each step. However, this approach quickly becomes infeasible as the number of houses increases, since there are 3 choices for each house and thus 3^n possible combinations.

Instead, we notice that the problem has an optimal substructure and overlapping subproblems—hallmarks of dynamic programming. For each house, the minimal cost to paint it depends only on the minimal cost of painting the previous house with a different color. This allows us to build up the solution efficiently by reusing previously computed results.

We shift from thinking about all combinations to incrementally building the minimum cost for each house and color, using prior results to avoid redundant work.

Solution Approach

• Step 1: Define State
  Let dp[i][j] represent the minimum cost to paint up to house i with color j.
• Step 2: Base Case
  For the first house (i=0), the cost for each color is simply costs[0][j] for j = 0, 1, 2.
• Step 3: Recurrence Relation
  For each subsequent house i and each color j, the cost is the cost of painting the current house with color j plus the minimum cost of painting the previous house with a different color:
  dp[i][j] = costs[i][j] + min(dp[i-1][k]) for all k ≠ j
• Step 4: Iteration
  Iterate through each house and update the dp table accordingly.
• Step 5: Result
  The answer is the minimum value in dp[n-1], which gives the minimal cost to paint all houses.
• Optimization
  Since each row of dp only depends on the previous row, we can optimize space by keeping only two rows or even just three variables.

Example Walkthrough

Let's consider the following costs matrix:

  costs = [
    [17, 2, 17],
    [16, 16, 5],
    [14, 3, 19]
  ]
  

• House 0: Costs are [17, 2, 17]
• House 1:
  • Red: 16 + min(2, 17) = 16 + 2 = 18
  • Blue: 16 + min(17, 17) = 16 + 17 = 33
  • Green: 5 + min(17, 2) = 5 + 2 = 7
  So, dp[1] = [18, 33, 7]
• House 2:
  • Red: 14 + min(33, 7) = 14 + 7 = 21
  • Blue: 3 + min(18, 7) = 3 + 7 = 10
  • Green: 19 + min(18, 33) = 19 + 18 = 37
  So, dp[2] = [21, 10, 37]
• The minimum total cost is 10, by painting house 0 blue, house 1 green, and house 2 blue.

Time and Space Complexity

• Brute-force Approach:
  For each house, we have 3 choices, leading to 3^n combinations. Checking each is exponential in time and not feasible for large n.
• Optimized DP Approach:
  We process each house once, and for each house, we consider 3 color options. This results in O(n) time complexity, where n is the number of houses.
  The space complexity is O(1) if we only keep the last row (since each row depends only on the previous), or O(n) if we store the full DP table.

Summary

The Paint House problem is elegantly solved using dynamic programming by realizing that the minimum cost to paint each house with a color depends only on the minimum costs of painting the previous house with the other two colors. By incrementally building up the solution and optimizing space, we avoid redundant work and achieve an efficient solution. This approach showcases the power of dynamic programming for problems with overlapping subproblems and optimal substructure.

Code Implementation

class Solution:
    def minCost(self, costs):
        if not costs:
            return 0
        n = len(costs)
        prev = costs[0][:]
        for i in range(1, n):
            curr = [0, 0, 0]
            curr[0] = costs[i][0] + min(prev[1], prev[2])
            curr[1] = costs[i][1] + min(prev[0], prev[2])
            curr[2] = costs[i][2] + min(prev[0], prev[1])
            prev = curr
        return min(prev)
      

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;
        int n = costs.size();
        vector<int> prev = costs[0];
        for (int i = 1; i < n; ++i) {
            vector<int> curr(3, 0);
            curr[0] = costs[i][0] + min(prev[1], prev[2]);
            curr[1] = costs[i][1] + min(prev[0], prev[2]);
            curr[2] = costs[i][2] + min(prev[0], prev[1]);
            prev = curr;
        }
        return min({prev[0], prev[1], prev[2]});
    }
};
      

class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;
        int n = costs.length;
        int[] prev = new int[]{costs[0][0], costs[0][1], costs[0][2]};
        for (int i = 1; i < n; i++) {
            int[] curr = new int[3];
            curr[0] = costs[i][0] + Math.min(prev[1], prev[2]);
            curr[1] = costs[i][1] + Math.min(prev[0], prev[2]);
            curr[2] = costs[i][2] + Math.min(prev[0], prev[1]);
            prev = curr;
        }
        return Math.min(prev[0], Math.min(prev[1], prev[2]));
    }
}
      

var minCost = function(costs) {
    if (!costs || costs.length === 0) return 0;
    let prev = costs[0].slice();
    for (let i = 1; i < costs.length; i++) {
        let curr = [0, 0, 0];
        curr[0] = costs[i][0] + Math.min(prev[1], prev[2]);
        curr[1] = costs[i][1] + Math.min(prev[0], prev[2]);
        curr[2] = costs[i][2] + Math.min(prev[0], prev[1]);
        prev = curr;
    }
    return Math.min(...prev);
};