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 的墙，花费 0，需要 2 单位时间。
总费用为 1 + 2 = 3。

示例 2：

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

提示：

  • 1 <= cost.length <= 500
  • cost.length == time.length
  • 1 <= cost[i] <= 10^6
  • 1 <= time[i] <= 500

解题思路

这是一道经典的动态规划问题。关键在于理解免费油漆匠的工作机制：只有在付费油漆匠工作时，免费油漆匠才能同时工作。

核心思路： 当付费油漆匠刷第 i 堵墙时，花费时间 time[i]，在这段时间内免费油漆匠最多能刷 time[i] 堵墙。因此，选择付费油漆匠刷第 i 堵墙实际上相当于"覆盖"了 time[i] + 1 堵墙（包括第 i 堵墙本身）。

状态定义： dp[i][j] 表示考虑前 i 堵墙，还需要刷 j 堵墙的最小费用。

状态转移： 对于第 i 堵墙，有两种选择：

  1. 不用付费油漆匠刷：dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])
  2. 用付费油漆匠刷：dp[i+1][max(0, j-time[i])] = min(dp[i+1][max(0, j-time[i])], dp[i][j] + cost[i])

优化：

  • 由于最多只需要付费刷 n/2 堵墙（剩下的可以免费刷），所以 j 的范围可以限制为 [0, n]
  • 可以使用滚动数组优化空间复杂度

代码实现

class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            vector<int> ndp(n + 1, INT_MAX);
            for (int j = 0; j <= n; j++) {
                if (dp[j] == INT_MAX) continue;
                // 不选择当前墙用付费油漆匠
                if (j + 1 <= n) {
                    ndp[j + 1] = min(ndp[j + 1], dp[j]);
                }
                // 选择当前墙用付费油漆匠
                int remain = max(0, j - time[i]);
                ndp[remain] = min(ndp[remain], dp[j] + cost[i]);
            }
            dp = ndp;
        }
        
        return dp[0];
    }
};

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(n):
            ndp = [float('inf')] * (n + 1)
            for j in range(n + 1):
                if dp[j] == float('inf'):
                    continue
                # 不选择当前墙用付费油漆匠
                if j + 1 <= n:
                    ndp[j + 1] = min(ndp[j + 1], dp[j])
                # 选择当前墙用付费油漆匠
                remain = max(0, j - time[i])
                ndp[remain] = min(ndp[remain], dp[j] + cost[i])
            dp = ndp
        
        return dp[0]

public class Solution {
    public int PaintWalls(int[] cost, int[] time) {
        int n = cost.Length;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = int.MaxValue;
        }
        
        for (int i = 0; i < n; i++) {
            int[] ndp = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                ndp[j] = int.MaxValue;
            }
            
            for (int j = 0; j <= n; j++) {
                if (dp[j] == int.MaxValue) continue;
                // 不选择当前墙用付费油漆匠
                if (j + 1 <= n) {
                    ndp[j + 1] = Math.Min(ndp[j + 1], dp[j]);
                }
                // 选择当前墙用付费油漆匠
                int remain = Math.Max(0, j - time[i]);
                ndp[remain] = Math.Min(ndp[remain], dp[j] + cost[i]);
            }
            dp = ndp;
        }
        
        return dp[0];
    }
}

var paintWalls = function(cost, time) {
    const n = cost.length;
    const memo = new Map();
    
    function dp(i, remain) {
        if (remain <= 0) return 0;
        if (i >= n) return Infinity;
        
        const key = i * 501 + remain;
        if (memo.has(key)) return memo.get(key);
        
        const paint = cost[i] + dp(i + 1, remain - 1 - time[i]);
        const skip = dp(i + 1, remain);
        
        const result = Math.min(paint, skip);
        memo.set(key, result);
        return result;
    }
    
    return dp(0, n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n²)
空间复杂度O(n)