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
- The key observation: when the paid painter paints wall
i, the free painter gainstime[i]units of work, i.e. it can painttime[i]more walls. - So a single paid job with time
tcoverst + 1walls: the wall itself plus the ones the free painter handles while it works. - Let
dp[j]be the minimum cost to coverjwalls. Choosing walligivesdp[j] = min(dp[j], dp[max(0, j - t - 1)] + cost[i]). - The answer is
dp[n]; clamping withmax(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 + 1walls, so the painters never need to be tracked independently. - Iterating
jupward: this is a 0/1 knapsack-style update, sojmust descend to avoid reusing the same wall. - Using
j - tinstead ofj - 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.