Paint House II

Updated on 03 July, 2025
Paint House II header image

Problem Statement

In this problem, we need to determine the minimum cost to paint a row of n houses, where each can be painted using one of the k different colors. Every distinct pair of adjacent houses must be painted with different colors, and the cost varies for painting each house with each specific color. This varied cost is given in an n x k matrix where each entry, such as costs[i][j], represents the cost of painting the i-th house with the j-th color. The challenge is to find a painting strategy that ensures adjacent houses are not the same color and the total painting cost is minimized.

Examples

Example 1

Input:

costs = [[1,5,3],[2,9,4]]

Output:

5

Explanation:

Paint house 0 into color 0, paint house 1 into color 2. Minimum cost: 1 + 4 = 5;
Or paint house 0 into color 2, paint house 1 into color 0. Minimum cost: 3 + 2 = 5.

Example 2

Input:

costs = [[1,3],[2,4]]

Output:

5

Constraints

  • costs.length == n
  • costs[i].length == k
  • 1 <= n <= 100
  • 2 <= k <= 20
  • 1 <= costs[i][j] <= 20

Approach and Intuition

To find the minimum cost of painting the houses without any two adjacent ones being the same color, we can follow a dynamic programming approach. Here are the detailed steps we can consider, based on the examples and constraints provided:

  1. Initialization:

    • Start with a dp array where dp[i][j] holds the minimum cost attained by painting house i with color j.
  2. Base Case:

    • The values of dp[0][j] are initialized to costs[0][j] for all j, since the first house can be painted with any color without any constraints from previous houses.
  3. Building the DP Table:

    • For each subsequent house i (from 1 to n-1), and each possible color j:
      • Calculate the minimum cost to paint the house i with color j by considering the cost of painting the previous house (i-1) with any color other than j.
      • This involves finding the minimum cost incurred for painting house i-1 with any color except j, and adding the cost of painting house i with color j.
  4. Transition:

    • dp[i][j] = costs[i][j] + min(dp[i-1][k]) for all k != j.
    • This formula helps in maintaining the minimum cost at each step while ensuring that no two adjacent houses have the same color.
  5. Result:

    • Once the dp table is complete, the minimum cost to paint all the houses will be min(dp[n-1][j]) where j varies over all colors.

This dynamic programming mechanism efficiently computes the minimal painting cost using the constraint that no two adjacent houses can have the same color, leveraging previously computed results to keep the runtime manageable. Given constraints, our approach fits well because it explores every color option for each house in a systematic manner, adhering to the given adjacency constraint.

Solutions

  • Java
java
class Solution {
    
    public int minimumCostPaint(int[][] costs) {
    
        if (costs.length == 0) return 0;
        int numColors = costs[0].length;
        int numHouses = costs.length;
    
        // Find initial min costs and indices for the first row.
        int prevLow = -1; int prevSecondLow = -1; int prevLowIndex = -1;
        for (int clr = 0; clr < numColors; clr++) {
            int costVal = costs[0][clr];
            if (prevLow == -1 || costVal < prevLow) {
                prevSecondLow = prevLow;
                prevLowIndex = clr;
                prevLow = costVal;
            } else if (prevSecondLow == -1 || costVal < prevSecondLow) {
                prevSecondLow = costVal;
            }
        }
    
        // Process all houses
        for (int houseIdx = 1; houseIdx < numHouses; houseIdx++) {
            int low = -1; int secondLow = -1; int lowIndex = -1;
            for (int clr = 0; clr < numColors; clr++) {
                int currentCost = costs[houseIdx][clr];
                if (clr == prevLowIndex) {
                    currentCost += prevSecondLow;
                } else {
                    currentCost += prevLow;
                }
                // Find new mins
                if (low == -1 || currentCost < low) {
                    secondLow = low;
                    lowIndex = clr;
                    low = currentCost;
                } else if (secondLow == -1 || currentCost < secondLow) {
                    secondLow = currentCost;
                }
            }
            prevLow = low;
            prevSecondLow = secondLow;
            prevLowIndex = lowIndex;
        }
    
        return prevLow;
    }
}

The provided Java program addresses the problem of finding the minimum cost to paint several houses, where each house can be painted with several colors at different costs, such that no two adjacent houses have the same color. The function minimumCostPaint expects an input matrix costs, where each row represents a house and each column represents the cost to paint that house with a specific color.

To solve this problem efficiently, the solution implements a dynamic programming approach:

  • Initialize variables to keep track of the lowest and second-lowest cost from the previous house, as well as the index of the lowest cost.
  • Iterate through the costs matrix:
    1. For the first house (base case), identify the first and second minimum painting costs and their corresponding color indices.
    2. For subsequent houses, update the painting cost considering the following:
      • If the current color index is the same as the previous lowest cost index, add the second lowest cost of the previous house to avoid painting the same color for adjacent houses.
      • Otherwise, add the lowest cost.
    3. During each iteration for a house, update the lowest and second-lowest values and their respective indices for use in the next house's calculation.

Ultimately, after processing all houses, prevLow contains the minimum cost for painting all houses according to the given constraints. This value is returned as the output of the function. This approach ensures a time-efficient solution by optimizing decisions at each step based on stored minimal values from the previous iteration, avoiding the exponential complexity of naive approaches.

Comments

No comments yet.