713540. Paint N House
Paint N House
Slug: distinct-coloring--170645
Difficulty: Medium
Id: 713540
Topic Tags: Dynamic Programming, Algorithms
Company Tags: Walmart, Google
Summary
The problem "Paint N House" is a classic dynamic programming problem. You are given n houses lined up in a row, and each house can be painted with one of three colors: red, blue, or green. The cost of painting each house with a particular color depends on the adjacent houses (i.e., left and right neighbors). Your goal is to find the minimum total cost required to paint all the houses such that no two adjacent houses have the same color.
Detailed Explanation
The key insight in this problem is to recognize that we can solve it by breaking it down into smaller subproblems. We will define a state variable dp[i][k] representing the minimum cost to paint the first i houses with the k-th color (1-indexed).
Here's the step-by-step breakdown:
- Initialize an
n x 3tabledpwherenis the number of houses and each row represents a house. - For each house, iterate through all three colors (
red,blue, andgreen). Calculate the minimum cost to paint this house with each color by considering the adjacent houses (if any). - For each color, calculate the minimum total cost by summing up the costs of painting the current house and the previous houses.
- Update the state variable
dp[i][k]with the minimum total cost calculated in step 3. - Finally, return the minimum value in the last row of the
dptable, which represents the overall minimum cost to paint all houses.
Here's a simple ASCII art diagram illustrating the problem:
House 1 | House 2 | ... | House n
+--------+--------+----+--------+
| Red | Blue |...| Green
| Blue | Red |...| ?
| ? | ? |...| ?
...
Time complexity: O(n), where n is the number of houses.
Space complexity: O(n), since we need to store the state variables for each house.
Optimized Solutions
Java
public class PaintNHouses {
public int minCost(int n, int[][] costs) {
int[][] dp = new int[n][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
}
return Math.min(Math.min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
}
}