⚡Flashcard Drill➔
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

  1. dp[i][j] is the minimum cost to paint the first i + 1 houses with house i in colour j.
  2. Naively dp[i][j] = costs[i][j] + min over c != j of dp[i-1][c], which is O(n k^2).
  3. Optimise by tracking the smallest and second-smallest values of the previous row together with the colour index of the smallest.
  4. 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 = m1 before m1 = prev[c], and use elif so 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems