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

  1. Let dp[i][j] be the minimum cost of painting houses 0..i with house i painted colour j.
  2. House i can only follow a different colour, so dp[i][j] = costs[i][j] + min(dp[i - 1][k]) over k != j.
  3. Only the previous row is needed, so three rolling values replace the full table.
  4. 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 costs should 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems