NeetCode #761LC-265Hard2-D Dynamic ProgrammingNC Algo100
← Back to All Problems#761 · #265 · Paint House II(粉刷房子 II)
📌 Problem Statement & Constraints
There are
n houses in a row and k colours. Painting house i with colour j costs costs[i][j], and no two adjacent houses may share a colour. Return the minimum total cost. Constraints: 1 <= n <= 100, 1 <= k <= 20, 1 <= costs[i][j] <= 20.💡 Core Algorithmic Approaches
dp[i][j]is the minimum cost to paint the firsti + 1houses with houseiin colourj.- Naively
dp[i][j] = costs[i][j] + min over c != j of dp[i-1][c], which is O(n k^2). - Optimise by tracking the smallest and second-smallest values of the previous row together with the colour index of the smallest.
- The transition then costs O(1): use the smallest unless its colour equals
j, in which case use the second smallest.
💻 Benchmark Python3 Implementation
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
if not costs:
return 0
n, k = len(costs), len(costs[0])
prev = costs[0][:] # first house: any colour
for i in range(1, n):
m1 = m2 = float("inf")
idx1 = -1
for c in range(k):
if prev[c] < m1:
m2, m1 = m1, prev[c]
idx1 = c
elif prev[c] < m2:
m2 = prev[c]
cur = [0] * k
for c in range(k):
cur[c] = costs[i][c] + (m2 if c == idx1 else m1)
prev = cur
return min(prev)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * k): one pass to find the two smallest previous costs plus one pass to build the current row.
💾 Space Complexity
O(k): two rows.
⚠️ Interview Pitfalls & Follow-ups
- Using only the single minimum: when the cheapest previous colour equals the current colour, the second minimum is required.
- Updating the two minima in the wrong order: set
m2 = m1beforem1 = prev[c], and useelifso one value is not counted twice. - Forgetting the first-house base case: the first house may use any colour at its raw cost.
- Settling for the O(k^2) transition: correct but slower; the two-minimum trick is the point of the problem.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.