NeetCode #662LC-256Medium1-D Dynamic ProgrammingNC Algo100
← Back to All Problems#662 · #256 · Paint House(粉刷房子)
📌 Problem Statement & Constraints
You are given an
n x 3 matrix costs where costs[i][j] is the cost of painting house i with colour j (colours 0, 1, 2). Paint every house so that no two adjacent houses share a colour, minimising the total cost. Constraints: 1 <= n <= 100, 1 <= costs[i][j] <= 20.💡 Core Algorithmic Approaches
- Let
dp[i][j]be the minimum cost of painting houses0..iwith houseipainted colourj. - House
ican only follow a different colour, sodp[i][j] = costs[i][j] + min(dp[i - 1][k])overk != j. - Only the previous row is needed, so three rolling values replace the full table.
- The answer is the minimum of the last row.
💻 Benchmark Python3 Implementation
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
if not costs:
return 0
prev = costs[0][:] # cost of painting house 0 with each colour
for i in range(1, len(costs)):
cur = [0, 0, 0]
cur[0] = costs[i][0] + min(prev[1], prev[2])
cur[1] = costs[i][1] + min(prev[0], prev[2])
cur[2] = costs[i][2] + min(prev[0], prev[1])
prev = cur
return min(prev)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a constant amount of work per house.
💾 Space Complexity
O(1): two rows of three values.
⚠️ Interview Pitfalls & Follow-ups
- Choosing the cheapest colour per house independently: the choice constrains the neighbours, so the previous row's colours must be considered.
- Omitting the empty-input guard: an empty
costsshould return 0, not raise an error. - Using
min(prev)for every colour: that permits the same colour as the previous house, which is illegal. - Allocating a full 2-D table: two rolling rows are enough because each row depends only on the previous one.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.