1473. Paint House III
Problem Description
You have a row of m
houses that need to be painted with one of n
colors (labeled from 1
to n
). Some houses are already painted and should not be repainted.
A neighborhood is defined as a maximal group of continuous houses painted with the same color. For example, if houses = [1,2,2,3,3,2,1,1]
, there are 5 neighborhoods: [{1}, {2,2}, {3,3}, {2}, {1,1}]
.
You are given:
- An array
houses
wherehouses[i]
represents:- The color of house
i
(if already painted) 0
if the house is not painted yet
- The color of house
- An
m x n
matrixcost
wherecost[i][j]
is the cost to paint housei
with colorj + 1
- An integer
target
representing the desired number of neighborhoods
Your task is to find the minimum cost to paint all unpainted houses such that the total number of neighborhoods equals exactly target
. If it's impossible to achieve exactly target
neighborhoods, return -1
.
The key constraints are:
- Already painted houses cannot be repainted
- You must create exactly
target
neighborhoods - Each unpainted house must be assigned one of the
n
available colors - The cost of painting each house with each color is given in the cost matrix
Intuition
The problem asks us to find the minimum cost to paint houses while maintaining exactly target
neighborhoods. This is a classic optimization problem with constraints, which suggests dynamic programming as a potential approach.
Let's think about what information we need to track as we process each house:
- Which house we're currently at - we need to make decisions for each house sequentially
- What color the previous house was painted - this determines whether we're continuing a neighborhood or starting a new one
- How many neighborhoods we've formed so far - we need exactly
target
neighborhoods at the end
This naturally leads to a 3-dimensional DP state: f[i][j][k]
representing the minimum cost to paint houses from index 0
to i
, where house i
is painted with color j
, and we've formed exactly k
neighborhoods.
The key insight is how neighborhoods are formed:
- If we paint the current house the same color as the previous house, we're extending the current neighborhood (no new neighborhood is created)
- If we paint the current house a different color than the previous house, we're starting a new neighborhood (neighborhood count increases by 1)
For each house, we have two scenarios:
- House is already painted: We can't change its color, so we only need to calculate the cost based on whether it forms a new neighborhood or not (cost is 0 since no painting is needed)
- House is not painted: We try all possible colors and add the painting cost, considering whether each color choice creates a new neighborhood
The transition between states depends on comparing the current house's color with the previous house's color:
- If
j == j0
(same color as previous):f[i][j][k] = f[i-1][j0][k] + cost
(if needed) - If
j != j0
(different color):f[i][j][k] = f[i-1][j0][k-1] + cost
(if needed)
By building up the solution house by house, tracking all possible color and neighborhood combinations, we can find the minimum cost to achieve exactly target
neighborhoods. The final answer is the minimum among all possible colors for the last house with exactly target
neighborhoods.
Learn more about Dynamic Programming patterns.
Solution Approach
We implement a 3D dynamic programming solution where f[i][j][k]
represents the minimum cost to paint houses from index 0
to i
, with house i
painted in color j
, forming exactly k
neighborhoods.
Initialization:
- Create a 3D array
f
with dimensions[m][n+1][target+1]
, initialized to infinity - For the first house (index 0):
- If unpainted:
f[0][j][1] = cost[0][j-1]
for each colorj
- If already painted:
f[0][houses[0]][1] = 0
- If unpainted:
Main DP Loop:
For each house i
from 1 to m-1
:
-
If house is unpainted (
houses[i] == 0
):- Try all possible colors
j
from 1 ton
- For each valid neighborhood count
k
from 1 tomin(target, i+1)
:- For each possible previous color
j0
:- If
j == j0
(same color, extend neighborhood):f[i][j][k] = min(f[i][j][k], f[i-1][j][k] + cost[i][j-1])
- If
j != j0
(different color, new neighborhood):f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1] + cost[i][j-1])
- If
- For each possible previous color
- Try all possible colors
-
If house is already painted (
houses[i] != 0
):- Set
j = houses[i]
(fixed color) - For each valid neighborhood count
k
:- For each possible previous color
j0
:- If
j == j0
(same color, extend neighborhood):f[i][j][k] = min(f[i][j][k], f[i-1][j][k])
- If
j != j0
(different color, new neighborhood):f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1])
- If
- For each possible previous color
- No painting cost is added since the house is already painted
- Set
Finding the Answer:
- After processing all houses, check
f[m-1][j][target]
for all colorsj
- Return the minimum value found
- If all values are infinity, return -1 (impossible to achieve target neighborhoods)
Key Optimizations:
- The neighborhood count
k
is bounded bymin(target+1, i+2)
since we can't have more neighborhoods than houses processed so far - We use 1-indexed colors to match the problem's color labeling (1 to n)
- The cost array uses 0-indexing, so we access
cost[i][j-1]
for colorj
The time complexity is O(m * n^2 * target)
and space complexity is O(m * n * target)
.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Input:
houses = [0, 2, 0]
(3 houses, middle one is already painted with color 2)cost = [[1, 10], [10, 1], [1, 10]]
(costs to paint each house with colors 1 or 2)target = 2
(we want exactly 2 neighborhoods)n = 2
(2 colors available)
Goal: Paint the unpainted houses (indices 0 and 2) to form exactly 2 neighborhoods with minimum cost.
DP Setup:
We create f[i][j][k]
where:
i
= house index (0 to 2)j
= color (1 or 2)k
= number of neighborhoods formed (1 or 2)
Step 1: Initialize for house 0 House 0 is unpainted, so we can paint it with either color:
f[0][1][1] = cost[0][0] = 1
(paint house 0 with color 1, forming 1 neighborhood)f[0][2][1] = cost[0][1] = 10
(paint house 0 with color 2, forming 1 neighborhood)
Step 2: Process house 1 House 1 is already painted with color 2 (no cost to add):
For k = 1
(maintaining 1 neighborhood):
f[1][2][1] = f[0][2][1] + 0 = 10
(previous house was also color 2, same neighborhood)
For k = 2
(forming 2 neighborhoods):
f[1][2][2] = f[0][1][1] + 0 = 1
(previous house was color 1, different from 2, new neighborhood)
Step 3: Process house 2 House 2 is unpainted, so we try both colors:
For color 1, k = 2
:
- From previous color 2 (different):
f[2][1][2] = f[1][2][1] + cost[2][0] = 10 + 1 = 11
For color 1, k = 3
:
- From previous color 2 (different):
f[2][1][3] = f[1][2][2] + cost[2][0] = 1 + 1 = 2
- But wait! We only want
target = 2
neighborhoods, so we don't considerk = 3
.
For color 2, k = 1
:
- From previous color 2 (same):
f[2][2][1] = f[1][2][1] + cost[2][1] = 10 + 10 = 20
For color 2, k = 2
:
- From previous color 2 (same):
f[2][2][2] = f[1][2][2] + cost[2][1] = 1 + 10 = 11
Step 4: Find the answer
We look at f[2][j][2]
for all colors j
:
f[2][1][2] = 11
(end with color 1, 2 neighborhoods)f[2][2][2] = 11
(end with color 2, 2 neighborhoods)
The minimum cost is 11.
Verification:
One optimal solution: Paint house 0 with color 1 (cost 1), house 1 is already color 2, paint house 2 with color 2 (cost 10). This gives us colors [1, 2, 2]
with 2 neighborhoods: [{1}, {2,2}]
. Total cost = 1 + 10 = 11.
Solution Implementation
1class Solution:
2 def minCost(
3 self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
4 ) -> int:
5 # Initialize DP table: dp[house_idx][color][num_neighborhoods]
6 # dp[i][j][k] = minimum cost to paint houses 0..i where house i has color j
7 # and forms exactly k neighborhoods
8 INF = float('inf')
9 dp = [[[INF] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
10
11 # Base case: handle the first house
12 if houses[0] == 0:
13 # First house is unpainted, try all possible colors
14 for color_idx, paint_cost in enumerate(cost[0], 1):
15 dp[0][color_idx][1] = paint_cost
16 else:
17 # First house is already painted, no cost needed
18 dp[0][houses[0]][1] = 0
19
20 # Fill the DP table for remaining houses
21 for house_idx in range(1, m):
22 if houses[house_idx] == 0:
23 # Current house is unpainted, try all possible colors
24 for current_color in range(1, n + 1):
25 # Try different numbers of neighborhoods (up to house_idx + 1)
26 for num_neighborhoods in range(1, min(target + 1, house_idx + 2)):
27 # Consider all possible colors of the previous house
28 for prev_color in range(1, n + 1):
29 if current_color == prev_color:
30 # Same color as previous house, no new neighborhood
31 dp[house_idx][current_color][num_neighborhoods] = min(
32 dp[house_idx][current_color][num_neighborhoods],
33 dp[house_idx - 1][prev_color][num_neighborhoods] + cost[house_idx][current_color - 1]
34 )
35 else:
36 # Different color from previous house, creates new neighborhood
37 dp[house_idx][current_color][num_neighborhoods] = min(
38 dp[house_idx][current_color][num_neighborhoods],
39 dp[house_idx - 1][prev_color][num_neighborhoods - 1] + cost[house_idx][current_color - 1]
40 )
41 else:
42 # Current house is already painted with a specific color
43 current_color = houses[house_idx]
44 # Try different numbers of neighborhoods
45 for num_neighborhoods in range(1, min(target + 1, house_idx + 2)):
46 # Consider all possible colors of the previous house
47 for prev_color in range(1, n + 1):
48 if current_color == prev_color:
49 # Same color as previous house, no new neighborhood
50 dp[house_idx][current_color][num_neighborhoods] = min(
51 dp[house_idx][current_color][num_neighborhoods],
52 dp[house_idx - 1][prev_color][num_neighborhoods]
53 )
54 else:
55 # Different color from previous house, creates new neighborhood
56 dp[house_idx][current_color][num_neighborhoods] = min(
57 dp[house_idx][current_color][num_neighborhoods],
58 dp[house_idx - 1][prev_color][num_neighborhoods - 1]
59 )
60
61 # Find the minimum cost among all possible colors for the last house
62 # with exactly target neighborhoods
63 min_cost = min(dp[-1][color][target] for color in range(1, n + 1))
64
65 # Return -1 if impossible, otherwise return the minimum cost
66 return -1 if min_cost >= INF else min_cost
67
1class Solution {
2 public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
3 // dp[i][j][k] represents the minimum cost to paint houses 0 to i
4 // where house i is painted with color j and we have k neighborhoods
5 int[][][] dp = new int[m][n + 1][target + 1];
6 final int INF = 1 << 30;
7
8 // Initialize all values to infinity
9 for (int[][] row : dp) {
10 for (int[] col : row) {
11 Arrays.fill(col, INF);
12 }
13 }
14
15 // Base case: initialize first house
16 if (houses[0] == 0) {
17 // If first house is not painted, try all colors
18 for (int color = 1; color <= n; ++color) {
19 dp[0][color][1] = cost[0][color - 1];
20 }
21 } else {
22 // If first house is already painted, no cost needed
23 dp[0][houses[0]][1] = 0;
24 }
25
26 // Fill the dp table for remaining houses
27 for (int houseIdx = 1; houseIdx < m; ++houseIdx) {
28 if (houses[houseIdx] == 0) {
29 // Current house is not painted, try all possible colors
30 for (int curColor = 1; curColor <= n; ++curColor) {
31 for (int neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
32 // Try all possible colors for previous house
33 for (int prevColor = 1; prevColor <= n; ++prevColor) {
34 if (curColor == prevColor) {
35 // Same color as previous house, neighborhoods count stays same
36 dp[houseIdx][curColor][neighborhoods] = Math.min(
37 dp[houseIdx][curColor][neighborhoods],
38 dp[houseIdx - 1][curColor][neighborhoods] + cost[houseIdx][curColor - 1]
39 );
40 } else {
41 // Different color from previous house, neighborhoods count increases by 1
42 dp[houseIdx][curColor][neighborhoods] = Math.min(
43 dp[houseIdx][curColor][neighborhoods],
44 dp[houseIdx - 1][prevColor][neighborhoods - 1] + cost[houseIdx][curColor - 1]
45 );
46 }
47 }
48 }
49 }
50 } else {
51 // Current house is already painted
52 int curColor = houses[houseIdx];
53 for (int neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
54 // Try all possible colors for previous house
55 for (int prevColor = 1; prevColor <= n; ++prevColor) {
56 if (curColor == prevColor) {
57 // Same color as previous house, neighborhoods count stays same
58 dp[houseIdx][curColor][neighborhoods] = Math.min(
59 dp[houseIdx][curColor][neighborhoods],
60 dp[houseIdx - 1][curColor][neighborhoods]
61 );
62 } else {
63 // Different color from previous house, neighborhoods count increases by 1
64 dp[houseIdx][curColor][neighborhoods] = Math.min(
65 dp[houseIdx][curColor][neighborhoods],
66 dp[houseIdx - 1][prevColor][neighborhoods - 1]
67 );
68 }
69 }
70 }
71 }
72 }
73
74 // Find the minimum cost among all possible colors for the last house
75 // with exactly target neighborhoods
76 int minCostResult = INF;
77 for (int color = 1; color <= n; ++color) {
78 minCostResult = Math.min(minCostResult, dp[m - 1][color][target]);
79 }
80
81 // Return -1 if no valid solution exists, otherwise return the minimum cost
82 return minCostResult >= INF ? -1 : minCostResult;
83 }
84}
85
1class Solution {
2public:
3 int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
4 // dp[i][j][k] represents the minimum cost to paint houses 0 to i
5 // where house i is painted with color j and forms k neighborhoods
6 const int INF = 0x3f3f3f3f;
7 int dp[m][n + 1][target + 1];
8 memset(dp, 0x3f, sizeof(dp));
9
10 // Initialize first house
11 if (houses[0] == 0) {
12 // First house is not painted, try all colors
13 for (int color = 1; color <= n; ++color) {
14 dp[0][color][1] = cost[0][color - 1];
15 }
16 } else {
17 // First house is already painted
18 dp[0][houses[0]][1] = 0;
19 }
20
21 // Process remaining houses
22 for (int i = 1; i < m; ++i) {
23 if (houses[i] == 0) {
24 // Current house is not painted, try all colors
25 for (int curColor = 1; curColor <= n; ++curColor) {
26 // Try different number of neighborhoods (up to target and i+1)
27 for (int neighborhoods = 1; neighborhoods <= min(target, i + 1); ++neighborhoods) {
28 // Try all possible colors for previous house
29 for (int prevColor = 1; prevColor <= n; ++prevColor) {
30 if (curColor == prevColor) {
31 // Same color as previous house, neighborhoods count stays the same
32 dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods],
33 dp[i - 1][prevColor][neighborhoods] + cost[i][curColor - 1]);
34 } else {
35 // Different color from previous house, creates a new neighborhood
36 dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods],
37 dp[i - 1][prevColor][neighborhoods - 1] + cost[i][curColor - 1]);
38 }
39 }
40 }
41 }
42 } else {
43 // Current house is already painted
44 int curColor = houses[i];
45 // Try different number of neighborhoods (up to target and i+1)
46 for (int neighborhoods = 1; neighborhoods <= min(target, i + 1); ++neighborhoods) {
47 // Try all possible colors for previous house
48 for (int prevColor = 1; prevColor <= n; ++prevColor) {
49 if (curColor == prevColor) {
50 // Same color as previous house, neighborhoods count stays the same
51 dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods],
52 dp[i - 1][prevColor][neighborhoods]);
53 } else {
54 // Different color from previous house, creates a new neighborhood
55 dp[i][curColor][neighborhoods] = min(dp[i][curColor][neighborhoods],
56 dp[i - 1][prevColor][neighborhoods - 1]);
57 }
58 }
59 }
60 }
61 }
62
63 // Find minimum cost among all possible colors for the last house with exactly target neighborhoods
64 int minCostResult = INF;
65 for (int lastColor = 1; lastColor <= n; ++lastColor) {
66 minCostResult = min(minCostResult, dp[m - 1][lastColor][target]);
67 }
68
69 // Return -1 if impossible to achieve target neighborhoods, otherwise return minimum cost
70 return minCostResult == INF ? -1 : minCostResult;
71 }
72};
73
1/**
2 * Finds the minimum cost to paint houses forming exactly target neighborhoods
3 * @param houses - Array where houses[i] is the color of house i (0 means unpainted)
4 * @param cost - 2D array where cost[i][j] is the cost to paint house i with color j+1
5 * @param m - Number of houses
6 * @param n - Number of available colors (1 to n)
7 * @param target - Target number of neighborhoods
8 * @returns Minimum cost to paint all houses, or -1 if impossible
9 */
10function minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number {
11 // Define infinity as a large number for impossible states
12 const INFINITY = 1 << 30;
13
14 // Initialize DP table: dp[houseIndex][color][neighborhoodCount]
15 // dp[i][j][k] represents minimum cost to paint houses 0..i where:
16 // - house i is painted with color j
17 // - there are exactly k neighborhoods formed
18 const dp: number[][][] = new Array(m)
19 .fill(0)
20 .map(() => new Array(n + 1)
21 .fill(0)
22 .map(() => new Array(target + 1).fill(INFINITY)));
23
24 // Base case: Initialize first house
25 if (houses[0] === 0) {
26 // First house is unpainted, try all colors
27 for (let color = 1; color <= n; ++color) {
28 // Painting first house creates exactly 1 neighborhood
29 dp[0][color][1] = cost[0][color - 1];
30 }
31 } else {
32 // First house is already painted
33 dp[0][houses[0]][1] = 0;
34 }
35
36 // Fill DP table for remaining houses
37 for (let houseIdx = 1; houseIdx < m; ++houseIdx) {
38 if (houses[houseIdx] === 0) {
39 // Current house is unpainted, try all possible colors
40 for (let currentColor = 1; currentColor <= n; ++currentColor) {
41 // Try all possible neighborhood counts (up to current house count)
42 for (let neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
43 // Check all possible colors of previous house
44 for (let previousColor = 1; previousColor <= n; ++previousColor) {
45 if (previousColor === currentColor) {
46 // Same color as previous house - no new neighborhood
47 dp[houseIdx][currentColor][neighborhoods] = Math.min(
48 dp[houseIdx][currentColor][neighborhoods],
49 dp[houseIdx - 1][currentColor][neighborhoods] + cost[houseIdx][currentColor - 1]
50 );
51 } else {
52 // Different color from previous house - creates new neighborhood
53 dp[houseIdx][currentColor][neighborhoods] = Math.min(
54 dp[houseIdx][currentColor][neighborhoods],
55 dp[houseIdx - 1][previousColor][neighborhoods - 1] + cost[houseIdx][currentColor - 1]
56 );
57 }
58 }
59 }
60 }
61 } else {
62 // Current house is already painted
63 const currentColor = houses[houseIdx];
64
65 // Try all possible neighborhood counts
66 for (let neighborhoods = 1; neighborhoods <= Math.min(target, houseIdx + 1); ++neighborhoods) {
67 // Check all possible colors of previous house
68 for (let previousColor = 1; previousColor <= n; ++previousColor) {
69 if (previousColor === currentColor) {
70 // Same color as previous house - no new neighborhood
71 dp[houseIdx][currentColor][neighborhoods] = Math.min(
72 dp[houseIdx][currentColor][neighborhoods],
73 dp[houseIdx - 1][currentColor][neighborhoods]
74 );
75 } else {
76 // Different color from previous house - creates new neighborhood
77 dp[houseIdx][currentColor][neighborhoods] = Math.min(
78 dp[houseIdx][currentColor][neighborhoods],
79 dp[houseIdx - 1][previousColor][neighborhoods - 1]
80 );
81 }
82 }
83 }
84 }
85 }
86
87 // Find minimum cost among all possible colors for the last house
88 let minimumCost = INFINITY;
89 for (let color = 1; color <= n; ++color) {
90 minimumCost = Math.min(minimumCost, dp[m - 1][color][target]);
91 }
92
93 // Return -1 if impossible, otherwise return the minimum cost
94 return minimumCost >= INFINITY ? -1 : minimumCost;
95}
96
Time and Space Complexity
Time Complexity: O(m × n² × target)
The analysis breaks down as follows:
- The outer loop iterates through
m
houses (from index 1 to m-1) - For each house, we iterate through up to
n
possible colors for the current house (variablej
) - For each color, we iterate through up to
target
possible neighborhood counts (variablek
) - For each neighborhood count, we iterate through
n
possible colors of the previous house (variablej0
) - The initialization phase for the first house takes
O(n)
time
Therefore, the overall time complexity is O(m × n × target × n) = O(m × n² × target)
Space Complexity: O(m × n × target)
The space complexity is determined by the 3D DP array f
:
- First dimension:
m
houses - Second dimension:
n + 1
colors (indexed from 0 to n) - Third dimension:
target + 1
neighborhood counts (indexed from 0 to target)
The array f
has dimensions [m][n+1][target+1]
, resulting in a space complexity of O(m × n × target)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Color Indexing Between Houses and Cost Arrays
One of the most common mistakes is confusion between the color indexing systems:
- The
houses
array uses 1-based indexing for colors (1 to n), with 0 indicating unpainted - The
cost
matrix uses 0-based indexing wherecost[i][j]
represents the cost to paint housei
with colorj+1
Pitfall Example:
# WRONG: Using color directly as index in cost array
if houses[house_idx] == 0:
for current_color in range(1, n + 1):
# This will cause IndexError or use wrong cost
painting_cost = cost[house_idx][current_color] # ❌ Wrong!
Solution:
# CORRECT: Subtract 1 when accessing cost array
if houses[house_idx] == 0:
for current_color in range(1, n + 1):
painting_cost = cost[house_idx][current_color - 1] # ✓ Correct!
2. Forgetting to Skip Painting Cost for Already Painted Houses
When a house is already painted, adding its painting cost is incorrect since we cannot repaint it.
Pitfall Example:
# WRONG: Adding cost even for already painted houses
if houses[house_idx] != 0:
current_color = houses[house_idx]
# Adding cost here is wrong!
dp[house_idx][current_color][num_neighborhoods] = min(
dp[house_idx][current_color][num_neighborhoods],
dp[house_idx - 1][prev_color][num_neighborhoods] + cost[house_idx][current_color - 1] # ❌
)
Solution:
# CORRECT: No cost added for already painted houses
if houses[house_idx] != 0:
current_color = houses[house_idx]
dp[house_idx][current_color][num_neighborhoods] = min(
dp[house_idx][current_color][num_neighborhoods],
dp[house_idx - 1][prev_color][num_neighborhoods] # ✓ No cost added
)
3. Incorrect Neighborhood Count Bounds
The maximum number of neighborhoods at house i
cannot exceed i+1
(one neighborhood per house). Using target+1
as the upper bound for all houses wastes computation and can lead to logic errors.
Pitfall Example:
# WRONG: Always iterating up to target+1 neighborhoods
for num_neighborhoods in range(1, target + 1): # ❌ Inefficient and potentially wrong
# This allows invalid states where neighborhoods > houses
Solution:
# CORRECT: Limit neighborhoods to min(target+1, house_idx+2)
for num_neighborhoods in range(1, min(target + 1, house_idx + 2)): # ✓
# This ensures we never have more neighborhoods than houses
4. Not Handling the Base Case Correctly
The first house requires special handling since it always forms exactly 1 neighborhood, and there's no previous house to consider.
Pitfall Example:
# WRONG: Trying to access previous house for index 0
for house_idx in range(m): # Starting from 0
for prev_color in range(1, n + 1):
# This will fail when house_idx = 0
dp[house_idx][current_color][k] = dp[house_idx - 1][prev_color][k] # ❌ Index -1!
Solution:
# CORRECT: Handle first house separately
if houses[0] == 0:
for color_idx, paint_cost in enumerate(cost[0], 1):
dp[0][color_idx][1] = paint_cost
else:
dp[0][houses[0]][1] = 0
# Then process remaining houses starting from index 1
for house_idx in range(1, m): # ✓ Start from 1
# ... rest of the logic
In a binary min heap, the minimum element can be found in:
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!