- 博客主页:誓则盟约
- 系列专栏:IT竞赛 专栏
- 关注博主,后期持续更新系列文章
- 如果有错误感谢请大家批评指出,及时修改
- 感谢大家点赞👍收藏⭐评论✍
2742.给墙壁刷油漆【困难】
题目:
给你两个长度为 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**6
1 <= time[i] <= 500
分析问题:
思路一:
首先,我们需要理解问题的本质是在给定成本和时间的列表情况下,找到满足一定体积需求的最小花费。这个问题通过定义一个 dfs
函数来解决,函数中的参数 i
表示当前考虑的物品索引,j
表示剩余需要的体积。
接下来,分析 dfs
函数的逻辑。当 j <= 0
时,表示剩余需要的体积已经满足要求,不需要再选择物品,所以返回 0
。当 i < 0
且 j > 0
时,表示没有物品可选但仍有剩余体积需求,这是不合法的情况,所以返回正无穷大 inf
。对于其他情况,有两种选择:一是选择当前物品,此时需要花费 cost[i]
,剩余需要的体积变为 j - time[i] - 1
,然后递归调用 dfs(i - 1, j - time[i] - 1)
;二是不选择当前物品,直接递归调用 dfs(i - 1, j)
。函数返回这两种选择中的最小值。
然后,要注意到使用了 @cache
装饰器进行记忆化搜索。这是为了避免重复计算相同的子问题,提高算法的效率。
最后,在 paintWalls
方法中,通过获取 cost
列表的长度 n
,然后调用 dfs(n - 1, n)
来计算最小的花费。
思路二:
首先,定义两个匿名函数 min
和 max
,分别用于求两个数中的最小值和最大值。
然后,获取 cost
列表的长度 n
,并初始化一个列表 f
。 f[0]
设为 0
, f[1]
到 f[n]
设为正无穷大 inf
。
接下来,通过遍历 cost
和 time
列表的对应元素 c
和 t
,进行动态规划的计算。
对于每个 c
和 t
,从 n
到 1
逆序遍历 f
列表。对于每个 j
,更新 f[j]
的值。更新的方式是取当前的 f[j]
和 f[max(j - t - 1, 0)] + c
中的最小值。 max(j - t - 1, 0)
表示在考虑当前时间 t
的情况下,能够完成的工作量对应的索引。通过这种方式,我们在每个位置 j
上,都找到了使用前 j
个物品能够达到的最小花费。
最后,函数返回 f[n]
,即使用所有物品能够达到的最小花费。
代码实现:
思路一代码实现:
class Solution:def paintWalls(self, cost: List[int], time: List[int]) -> int:@cache # 记忆化搜索def dfs(i: int, j: int) -> int: # j 表示剩余需要的体积if j <= 0: # 没有约束,后面什么也不用选了return 0if i < 0: # 此时 j>0,但没有物品可选,不合法return infreturn min(dfs(i - 1, j - time[i] - 1) + cost[i], dfs(i - 1, j))n = len(cost)return dfs(n - 1, n)
思路二代码实现:
class Solution:def paintWalls(self, cost: List[int], time: List[int]) -> int:# 定义一个匿名函数min,用于求两个数的最小值min = lambda a, b: b if b < a else a# 定义一个匿名函数max,用于求两个数的最大值max = lambda a, b: b if b > a else an = len(cost)# 初始化一个列表f,f[0]为0,f[1]到f[n]为正无穷大f = [0] + [float('inf')] * n# 遍历cost和time列表的对应元素for c, t in zip(cost, time):# 从n到1逆序遍历f列表for j in range(n, 0, -1):# 更新f[j]的值,取当前f[j]和f[max(j - t - 1, 0)] + c的最小值f[j] = min(f[j], f[max(j - t - 1, 0)] + c)# 返回f[n],即完成所有工作的最小花费return f[n]
总结:
思路一代码详解:
- 定义了一个内部的
dfs
函数,该函数使用了记忆化搜索(通过@cache
装饰器实现)。dfs
函数接受两个参数:i
表示当前考虑的物品索引,j
表示剩余需要的体积。 - 在
dfs
函数中,如果j <= 0
,表示剩余需要的体积已经满足要求,不需要再选择物品,返回0
。 - 如果
i < 0
且j > 0
,表示没有物品可选但仍有剩余体积需求,这种情况是不合法的,返回inf
(表示正无穷大)。 - 对于其他情况,有两种选择:
- 选择当前物品(索引为
i
),那么需要花费cost[i]
,并且剩余需要的体积变为j - time[i] - 1
,然后递归调用dfs(i - 1, j - time[i] - 1)
。 - 不选择当前物品,直接递归调用
dfs(i - 1, j)
。
- 选择当前物品(索引为
- 最后,函数返回这两种选择中的最小值。
- 在
paintWalls
方法中,首先获取cost
列表的长度n
,然后调用dfs(n - 1, n)
来计算最小的花费。
总的来说,这段代码的目的是通过递归的方式,在考虑每个物品的选择与否的情况下,计算出满足剩余体积需求的最小花费。记忆化搜索的使用可以避免重复计算,提高算法的效率。
考点:
- 动态规划:两段代码都运用了动态规划的思想来解决问题。通过定义合适的状态(如代码中的
f
数组)和状态转移方程(如更新f[j]
的值),来逐步求解最优解。 - 函数定义与使用:代码中定义了匿名函数(如
min
和max
函数)来简化比较和操作。 - 列表操作:涉及到列表的初始化、遍历(正序和逆序)以及元素的更新。
- 逻辑推理与问题分析:需要理解问题的要求,找出合适的解法,并将其转化为代码实现。
收获:
- 深入理解动态规划的概念和应用:通过实际解决这个问题,更加熟悉如何根据问题的特点定义状态和状态转移方程,从而有效地运用动态规划来求解最优解。
- 提高函数使用和定义的能力:学会了使用匿名函数来简洁地表达一些常见的操作,增强了代码的可读性和简洁性。
- 增强对列表数据结构的操作能力:包括列表的初始化、遍历和元素的修改,能够更加熟练地运用列表来解决实际问题。
- 培养逻辑思维和问题分析能力:在理解问题的基础上,能够将其转化为有效的算法和代码实现,提高了解决复杂问题的能力。
- 学会从不同的角度思考问题:两段代码虽然都解决了同一个问题,但实现方式略有不同,通过对比学习,可以拓宽解题思路,提高解决问题的灵活性。