
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:
Initialization:
- Start with a
dp
array wheredp[i][j]
holds the minimum cost attained by painting housei
with colorj
.
- Start with a
Base Case:
- The values of
dp[0][j]
are initialized tocosts[0][j]
for allj
, since the first house can be painted with any color without any constraints from previous houses.
- The values of
Building the DP Table:
- For each subsequent house
i
(from 1 ton-1
), and each possible colorj
:- Calculate the minimum cost to paint the house
i
with colorj
by considering the cost of painting the previous house (i-1
) with any color other thanj
. - This involves finding the minimum cost incurred for painting house
i-1
with any color exceptj
, and adding the cost of painting housei
with colorj
.
- Calculate the minimum cost to paint the house
- For each subsequent house
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.
Result:
- Once the
dp
table is complete, the minimum cost to paint all the houses will bemin(dp[n-1][j])
wherej
varies over all colors.
- Once the
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
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:
- For the first house (base case), identify the first and second minimum painting costs and their corresponding color indices.
- 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.
- 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.
No comments yet.