Leetcode 2742 漆房子

题目概述

Leetcode 2742

You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

• A paid painter that paints the i^th wall in time[i] units of time and takes cost[i] units of money.

• A free painter that paints any wall in 1 unit of time at a cost of 0. But the free painter can only be used if the paid painter is already occupied.

Return the minimum amount of money required to paint the n walls.

Constraints:

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

思路 & 代码实现

方法1：Top-Down Dynamic Programming

按照动态规划的解决问题思路，我们需要先定义子问题的状态。不妨假设油漆工按照索引由小到大的顺序工作，如此便可以自然得出第一个状态参数是当前面对的这面墙的索引值。除此之外显然还需要一个量用于判定整个漆墙工作是否完成，那便是已漆墙的个数。这里可以用i, painted两个变量指代。

根据题意可以推理出对于每一面墙来说，存在两种被漆的可能：

• 被付费油漆工漆
• 被免费油漆工漆

而免费油漆工的漆墙次数其实取决于付费油漆工，或者更准确地说，免费油漆工的漆墙次数不会超过付费油漆工的漆墙次数。而如果希望成本最小化，在付费油漆工漆墙的这段时间内，免费油漆工必定会一直工作。所以我们只需要关注付费油漆工的行为即可。而对于付费油漆工来说，每遇到一面墙他都可以做出两种选择：漆，或不漆。假设墙的总数为n，根据这两种不同的行为，我们可以推导出如下两种不同的状态变化：

• 选择漆第i面墙，那么在面对第i + 1面墙时，已漆的墙数为 painted + 1 + time[i], 当前成本增加cost[i]
• 选择不漆第i面墙， 那么在面对第i + 1面墙时，已漆的墙数为 painted, 当前成本不变

按照自顶向下的解决问题思路，定义递归函数dp，传入其中的参数为i，painted。递归终止的条件有以下两种：

• painted >= n, 这代表所有的墙都已被漆完，无需再进行任何工作，此时的后续成本为0。
• i >= n, 注意这个条件要在上一个条件之后，此时所处的索引已经位于范围之外，这表明尚有墙未被漆完，选择不漆的墙数过多了。故此种情况不能满足题目要求要被舍弃，而因为最终答案是要求最低成本，所以为保证此种情况被舍弃，返回inf。

同时为避免重复计算，需要记忆已经计算的结果，python中可选择@cache装饰器。代码实现如下：

Time complexity: O(n^2)

Space complexity: O(n^2)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)

        @cache
        def dp(i, painted):
            if painted >= n:
                return 0
            if i >= n:
                return inf
            # choose to paint current wall
            paint = cost[i] + dp(i + 1, painted + 1 + time[i])  
            # choose to ignore current wall
            not_paint = dp(i + 1, painted)  
            return min(paint, not_paint)

        return dp(0, 0)

顺利通过。

方法2: Bottom-Up Dynamic Programming

自底向上的动态规划采用迭代的方式，用dp数组记录每一个子问题的状态。与自顶向下的记忆化搜索不同，迭代则需要从最小的子问题开始依次向上求解，直到得出最终问题的答案。虽然在子问题结构上解决问题的方向不同，但是状态转移的方式是一样的，所以可以参考方法1中的思路。

首先，方法1中的dp函数传入了两个参数i和painted，那么与之相对应的dp数组将存在两个维度，分别表示方法1中的两个参数。接下来定义dp[i][j]表示的状态：漆到第i面墙，且已漆j面墙时，接下来为完成任务所需的最低成本。接下来考虑初始状态，对应的是dp函数中不符合条件返回的部分，也即墙的索引值超出范围时尚未漆完全部的墙的情况。用代码实现如下:

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for painted in range(n):
    dp[n][painted] = inf

这里dp数组的长度为n+1而不是n的原因是需要超出索引范围的情况作为初始状态（与dp函数的返回条件对应）。而因为dp[n][n]表示的含义是刚好在最后一面墙时完成所有漆墙任务，所以符合题意，后续的最低成本为0。接下来思考状态转移，假设当前的状态为dp[i][painted]，也即面对第i面墙时已漆painted面墙的状态。那么还是分为两种情况：

• 不漆第i面墙，则后续最低成本为面对第i + 1面墙，且已漆painted面墙时的后续最低成本
• 漆第i面墙，则后续最低成本为面对第i + 1面墙，且已漆painted + 1 + time[i]面墙时的后续最低成本加上漆当前这面墙的成本cost[i]

最后在两种情况中选择所需成本最少的那一个。解释一下第二种情况：painted + 1 + time[i]中1表示付费油漆工漆的一面墙，time[i]表示的是在付费油漆工漆这面墙时免费油漆工可以漆的墙数。加起来以后表示的是上一个状态已经漆的墙数。这里需要注意一个细节：此结果有可能大于n，所以需要判断一下，如果超过了就修改成n。状态转移的代码实现如下：

dp[i][painted] = min(dp[i+1][painted], dp[i+1][painted+1+time[i]] + cost[i])

最后需要明确按照当前的状态定义，最终所需的结果应该是保存在dp[0][0]中的，也即面对第0面墙，且尚未漆任何墙时为完成任务所需的最低成本。因此需要注意i与painted都应按照从大到小的顺序进行循环。最终代码实现如下：

Time complexity: O(n^2)

Space complexity: O(n^2)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        # dp[i][j], i th wall, j painted, minimum cost
        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

        for painted in range(n):
            dp[n][painted] = inf

        for i in range(n-1, -1, -1):
            for painted in range(n, -1, -1):
                dp[i][painted] = min(dp[i+1][painted], dp[i+1][min(n, painted+1+time[i])] + cost[i])

        return dp[0][0]

顺利通过。

方法3：Space-Optimized Dynamic Programming

可以注意到方法2中dp[i][*]的状态转移只取决于dp[i+1][*]，所以可以将i这一维度压缩，将空间复杂度优化到 $O(n)$。具体实现方式如下:

Time complexity: O(n^2)

Space complexity: O(n)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        prev = [inf for _ in range(n+1)]
        prev[-1] = 0
        cur = [0 for _ in range(n+1)]

        for i in range(n-1, -1, -1):
            for painted in range(n, -1, -1):
                cur[painted] = min(prev[painted], prev[min(n, painted+1+time[i])] + cost[i])
            prev = cur[:]

        return prev[0]

这里prev数组对应的是原先的dp[i + 1]，cur数组对应的是dp[i]。

细节：prev = cur[:]处不能写成prev = cur，因为这样prev并不是复制了cur这个数组，而是获得了cur这个数组的引用。这会导致后续修改cur数组的同时prev也被修改，而cur数组中的元素更新需要依赖原本的prev数组中保存的信息，所以最终会导致答案出错。

顺利通过。