#2742

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Painting the Walls

Compute the minimum cost to paint all walls using a paid and free painter with state transition dynamic programming.

Problem Statement

You are given two integer arrays, cost and time, each of length n, representing the painting cost and time for n walls. There are two painters available: one charges the given cost per wall, while the other can paint walls for free but only works sequentially without overlapping the paid painter. Determine the minimum total cost required to paint all walls.

Each wall can be assigned to either painter, but the free painter can only paint walls consecutively and must finish before switching. Find a strategy that schedules the walls optimally and returns the lowest money spent, taking both the cost array and time array into account.

Examples

Example 1

Input: cost = [1,2,3,2], time = [1,2,3,2]

Output: 3

The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.

Example 2

Input: cost = [2,3,4,2], time = [1,1,1,1]

Output: 4

The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.

Constraints

1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 106
1 <= time[i] <= 500

Solution Approach

Define DP states

Create a dynamic programming array dp[i] representing the minimum cost to paint the first i walls. Each state captures the scenario where the paid painter paints the current wall and the free painter paints a consecutive segment.

Transition and recurrence

For each wall i, consider all segments ending at i that the free painter could have painted. Update dp[i] as the minimum of dp[j] plus the cost of walls outside the free segment, ensuring we account for the total time constraint for both painters.

Compute final answer

After filling dp for all walls, dp[n] contains the minimum total cost. This approach efficiently breaks the problem into smaller subproblems, using the state transition DP pattern to track optimal costs for all possible painter assignments.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n)

Time complexity is O(n^2) because for each wall, we check all possible free painter segments. Space complexity is O(n) for the DP array storing minimum costs up to each wall.

What Interviewers Usually Probe

Can you explain how you are tracking subproblem states for both painters?
What is your plan for ensuring the free painter's consecutive painting constraint is respected?
How does your DP formulation guarantee the minimum total cost across all walls?

Common Pitfalls or Variants

Common pitfalls

Ignoring that the free painter must paint walls consecutively can lead to invalid cost calculations.
Failing to include all possible segments for the free painter in state transitions results in suboptimal DP updates.
Assuming constant-time updates instead of iterating segments can produce incorrect time complexity estimates.

Follow-up variants

Change the problem to allow multiple free painters with overlapping constraints.
Introduce variable cost reductions if the paid painter paints multiple walls consecutively.
Add a limit on total time each painter can work, requiring additional DP dimensions.

FAQ

What is the best approach to solve Painting the Walls efficiently?

Using state transition dynamic programming, track the minimum cost for each wall considering segments the free painter can paint consecutively.

Why is the free painter constraint important in DP?

Because the free painter can only paint consecutive walls, each DP state must reflect valid segments, ensuring accurate cost calculation.

Can this problem be solved with a greedy approach?

A greedy approach may fail because selecting walls individually ignores optimal segments, making DP necessary to minimize total cost.

What is the time and space complexity for Painting the Walls DP solution?

Time complexity is O(n^2) due to checking all segments per wall, and space complexity is O(n) for storing DP states.

How do I debug incorrect DP updates in Painting the Walls?

Verify that all valid consecutive segments for the free painter are considered and that each dp[i] correctly accumulates minimal cost from previous states.

terminal

Solution

Solution 1: Memorization

We can consider whether each wall is painted by a paid painter or a free painter. Design a function $dfs(i, j)$, which means that from the $i$th wall, and the current remaining free painter working time is $j$, the minimum cost of painting all the remaining walls. Then the answer is $dfs(0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if n - i <= j:
                return 0
            if i >= n:
                return inf
            return min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1))

        n = len(cost)
        return dfs(0, 0)

Continue Practicing

#2741 special permutations #2746 decremental string concatenation #2750 ways to split array into good subarrays