Painting the Walls

How it works

Notice that this problem resembles a 0/1 knapsack. Each wall is an item with a cost and a benefit (how many walls it covers). We need to cover exactly n walls with minimum total cost.

We can optimize space by using a 1D array. The key is to iterate remain in reverse order so that we do not overwrite values we still need in the current iteration.

Steps

1. Create a 1D DP array of size n + 2 initialized to infinity, except dp[0] = 0.
2. For each wall i, iterate remain from n down to 1.
3. Update dp[remain] = min(dp[remain], cost[i] + dp[max(remain - 1 - time[i], 0)]). This represents the choice of painting wall i with the paid painter.
4. The reverse iteration ensures we use the previous iteration's values for the paint choice.
5. Return dp[n].

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n)

Things to watch for

Misunderstanding the Free Painter's Role

A critical insight is that when the paid painter paints wall i taking time[i] units, the free painter can paint time[i] additional walls simultaneously. Many fail to realize that choosing wall i for the paid painter effectively covers 1 + time[i] walls total, not just 1 wall.

Integer Overflow When Adding to Infinity

When using Integer.MAX_VALUE or similar to represent infinity, adding cost[i] to it causes integer overflow, resulting in negative values and incorrect answers. Always check if the value is infinity before performing addition, or use a sufficiently large but safe sentinel value.

Iterating in Wrong Direction for Space Optimization

In the 1D DP optimization, iterating remain from 1 to n (forward) instead of from n to 1 (backward) causes incorrect results. Forward iteration uses values from the current iteration rather than the previous one, violating the DP recurrence. The reverse iteration ensures we use the untouched previous-iteration values.

Not Capping Negative Remain Values

When remain - 1 - time[i] becomes negative, it means all walls are covered. Failing to cap this at 0 leads to accessing negative indices in the DP array. Always use max(remain - 1 - time[i], 0) to handle cases where the free painter's contribution exceeds the remaining walls.

Treating This as a Standard Knapsack Problem

While this problem resembles 0/1 knapsack, the transition is different because time values affect how much work gets done, not just costs. Applying the standard knapsack recurrence without accounting for the free painter's parallel work leads to incorrect solutions.

from typing import List

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [float("inf")] * (n + 2)
        dp[0] = 0

        for i in range(n):
            for remain in range(n, 0, -1):
                paint = cost[i] + dp[max(remain - 1 - time[i], 0)]
                dp[remain] = min(paint, dp[remain])

        return dp[n]

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        vector<int> dp(n + 2, INT_MAX);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int remain = n; remain > 0; remain--) {
                int paint = dp[max(remain - 1 - time[i], 0)];
                if (paint != INT_MAX) paint += cost[i];
                dp[remain] = min(paint, dp[remain]);
            }
        }

        return dp[n];
    }
};