⚡Flashcard Drill➔
NeetCode #750LC-2742Hard2-D Dynamic Programming
← Back to All Problems

#750 · #2742 · Painting the Walls(给墙壁刷油漆)

📌 Problem Statement & Constraints

You must paint n walls. A paid painter paints wall i in time[i] units and charges cost[i]; while the paid painter is busy, a free painter paints any wall in one time unit at no cost. Return the minimum cost to paint every wall. Constraints: 1 <= n <= 500, 1 <= cost[i] <= 10^6, 1 <= time[i] <= 500.

💡 Core Algorithmic Approaches

  1. The key observation: when the paid painter paints wall i, the free painter gains time[i] units of work, i.e. it can paint time[i] more walls.
  2. So a single paid job with time t covers t + 1 walls: the wall itself plus the ones the free painter handles while it works.
  3. Let dp[j] be the minimum cost to cover j walls. Choosing wall i gives dp[j] = min(dp[j], dp[max(0, j - t - 1)] + cost[i]).
  4. The answer is dp[n]; clamping with max(0, ...) discards any surplus capacity.

💻 Benchmark Python3 Implementation

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for c, t in zip(cost, time):
            for j in range(n, 0, -1):          # descending: each wall used once
                # this job covers its own wall plus t walls for the free painter
                dp[j] = min(dp[j], dp[max(0, j - t - 1)] + c)
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): n jobs, each updating O(n) coverage states.
💾 Space Complexity
O(n): one coverage array.

⚠️ Interview Pitfalls & Follow-ups

  • Modelling the two painters separately: the trick is that one paid job covers t + 1 walls, so the painters never need to be tracked independently.
  • Iterating j upward: this is a 0/1 knapsack-style update, so j must descend to avoid reusing the same wall.
  • Using j - t instead of j - t - 1: the paid painter also paints its own wall, hence the extra one.
  • Not clamping with max(0, ...): the free painter can cover more walls than remain, and that surplus is simply wasted.
⚡
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