LeetCode 265: Paint House II
LeetCode 265 Solution Explanation
Explanation
In this problem, we are given a row of n houses, each house can be painted with one of k colors. The cost of painting each house with a certain color is represented by a n x k cost matrix. We need to paint all houses such that no two adjacent houses have the same color, and the total cost is minimized.
To solve this problem, we can use dynamic programming. We will maintain a 2D dp array where dp[i][j] represents the minimum cost of painting the first i houses with the ith house painted with color j. At each step, we update the dp array based on the minimum cost of painting the current house with each color considering the costs of the previous houses.
Algorithm:
- Initialize the dp array of size n x k with all values set to infinity except for the first row which is the same as the costs matrix.
- Iterate over the houses starting from the second house.
- For each house, iterate over the colors and calculate the minimum cost of painting the current house with each color considering the costs of the previous houses with different colors.
- Update the dp array with the minimum cost for each house and color combination.
- Finally, return the minimum cost from the last row of the dp array.
Time Complexity: O(n * k^2) where n is the number of houses and k is the number of colors. Space Complexity: O(n * k) for the dp array.
Java
LeetCode 265 Solutions in Java, C++, Python
class Solution {
public int minCostII(int[][] costs) {
if (costs == null || costs.length == 0) {
return 0;
}
int n = costs.length;
int k = costs[0].length;
int[][] dp = new int[n][k];
for (int j = 0; j < k; j++) {
dp[0][j] = costs[0][j];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < k; j++) {
dp[i][j] = Integer.MAX_VALUE;
for (int prev = 0; prev < k; prev++) {
if (prev != j) {
dp[i][j] = Math.min(dp[i][j], dp[i-1][prev] + costs[i][j]);
}
}
}
}
int minCost = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
minCost = Math.min(minCost, dp[n-1][j]);
}
return minCost;
}
}Interactive Code Editor for LeetCode 265
Improve Your LeetCode 265 Solution
Use the editor below to refine the provided solution for LeetCode 265. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...