Paint House II

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

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;
    }
}