给墙壁刷油漆

标签: 数组 动态规划

难度: Hard

给你两个长度为 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] <= 106
  • 1 <= time[i] <= 500

Submission

运行时间: 570 ms

内存: 16.1 MB

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n=len(cost)
        f=[0]+[inf]*n
        for t,c in zip(time,cost):
            t=min(t+1,n)
            for x in range(n,-1,-1):
                if x>=t:
                    f[x]=min(f[x],f[x-t]+c)
                else:
                    f[x]=min(f[x],c)
        return f[n]

Explain

这道题目使用了动态规划来解决。定义 dp 数组 f，其中 f[x] 表示最小成本以涂满 x 块墙。初始化 f[0] 为 0 表示没有墙时无需成本，其余为无穷大表示初始状态下未知。对于每一对 (time[i], cost[i])，我们考虑这堵墙由付费油漆匠刷，然后更新 dp 数组。如果当前时间 t 可以被安排，则更新 f[x] 为 '用更少的时间完成 x 块墙的最小成本'。否则，更新为 '在给定时间内刷 x 块墙的成本'。最后，返回 f[n]，即涂满 n 块墙的最小成本。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        # 初始化DP数组，f[0]为0，其余为无穷大
        f = [0] + [float('inf')] * n
        # 遍历每一堵墙的成本和时间
        for t, c in zip(time, cost):
            # 由于免费油漆匠只能工作t+1时间单位，确保不超过n
            t = min(t + 1, n)
            # 从后向前更新DP数组，避免覆盖
            for x in range(n, -1, -1):
                if x >= t:
                    # 计算当前墙由付费油漆匠刷，更新成本
                    f[x] = min(f[x], f[x-t] + c)
                else:
                    # 如果当前墙由免费油漆匠刷，更新最小成本
                    f[x] = min(f[x], c)
        # 返回涂满n堵墙的最小开销
        return f[n]

Explore

状态定义的选择基于问题的目标和约束来制定。在本题中，目标是最小化涂满 n 块墙的成本。将状态定义为 '涂满 x 块墙的最小成本' 允许我们逐步构建解决方案，每次涂墙都基于先前的最优结果。这种方法确保了每个子问题（涂满 x 块墙）都以全局最优的方式被解决，使得动态规划成为解决这类优化问题的有效工具。

在动态规划中从后向前更新是为了保证在计算 f[x] 时使用的是本轮之前的值（即上一轮的结果），而不是本轮已经更新过的值。如果从前向后更新，当我们尝试用 f[x-t] 来更新 f[x] 时，f[x-t] 可能已经在本轮被更新过，这会导致使用错误的信息进行计算，破坏了状态转移的正确性。从后向前则确保每次使用的都是未被本轮更新的旧值，从而保证结果的正确性。

t 的值代表油漆匠可以在给定时间内涂的最大墙块数。t+1 是因为如果油漆匠可以在 t 时间单位内工作，那么他可以涂 t+1 块墙（包括起始时间点）。将 t 限制为 min(t + 1, n) 是为了确保不超出总墙块数 n，从而避免不必要的计算和潜在的数组越界错误。这种设置优化了算法的性能，确保了计算的实际需求与问题规模相匹配，同时保证了算法的结果正确性。

如果 f[n] 在算法执行完毕后仍然是无穷大，这意味着在给定的资源和条件下，涂满 n 块墙是不可能的。这可能因为没有足够的时间或成本过高。在实际应用中，应当检查这种情况，并向用户报告涂满所有墙是无法实现的，或者需要重新考虑资源和条件的配置。