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.

#2742

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

给墙壁刷油漆

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：一位需要付费的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。一位免费的油漆匠，刷任意一堵墙的时间…

数组动态规划

题目描述

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

一位需要付费的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位免费的油漆匠，刷任意一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠工作时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。

示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。

提示：

1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 10⁶
1 <= time[i] <= 500

lightbulb

解题思路

方法一：记忆化搜索

我们可以考虑每一堵墙是给付费油漆匠刷还是给免费油漆匠刷，设计一个函数 $dfs(i, j)$ ，表示从第 $i$ 堵墙开始，且当前剩余的免费油漆匠工作时间为 $j$ 时，刷完剩余所有墙壁的最小开销。那么答案为 $dfs(0, 0)$ 。

函数 $dfs(i, j)$ 的计算过程如下：

如果 $n - i \le j$ ，表示剩余的墙壁不超过免费油漆匠的工作时间，那么剩余的墙壁都由免费油漆匠刷，开销为 $0$ ；
如果 $i \ge n$ ，返回 $+\infty$ ；
否则，如果第 $i$ 堵墙由付费油漆匠刷，开销为 $cost[i]$ ，那么 $dfs(i, j) = dfs(i + 1, j + time[i]) + cost[i]$ ；如果第 $i$ 堵墙由免费油漆匠刷，开销为 $0$ ，那么 $dfs(i, j) = dfs(i + 1, j - 1)$ 。

注意，参数 $j$ 可能小于 $0$ ，因此，在实际编码过程中，除了 $Python$ 语言外，我们对 $j$ 加上一个偏移量 $n$ ，使得 $j$ 的取值范围为 $[0, 2n]$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

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)

speed

复杂度分析

指标	值
时间	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.
空间	O(n)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2741 特别的排列 #2746 字符串连接删减字母 #2750 将数组划分成若干好子数组的方式