这道题的核心是将其转化为0-1 背包问题。每当付费油漆匠工作 time[i]time[i]time[i] 时间，他不仅刷完了一堵墙，还额外赠送了免费油漆匠刷 time[i]time[i]time[i] 堵墙的时间。因此，雇佣第 iii 个工匠的实际贡献是覆盖了 1+time[i]1 + time[i]1+time[i] 堵墙。
我们的目标是：从 nnn 堵墙中选出若干项目，使得它们的总覆盖数 ∑(1+time[i])≥n\sum (1 + time[i]) \ge n∑(1+time[i])≥n，且总 cost 最小。
TypeScript 实现
【typescript】
 function paintWalls(cost: number[], time: number[]): number {
    const n = cost.length;
    // dp[j] 表示覆盖 j 堵墙所需的最小开销
    // 初始化为最大值，dp[0] 为 0
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 0; i < n; i++) {
        const c = cost[i];
        const t = time[i] + 1; // 付费刷一堵，免费刷 time[i] 堵
        
        // 倒序遍历，防止重复计算（0-1背包标准写法）
        for (let j = n; j > 0; j--) {
            // 如果覆盖数超过 n，统一按 n 计算
            const covered = Math.max(0, j - t);
            dp[j] = Math.min(dp[j], dp[covered] + c);
        }
    }
    return dp[n];
}
逻辑解析
2. 转化思路：免费油漆匠不需要钱，但他的“额度”由付费油漆匠提供。付费匠刷一堵墙耗时 TTT，这意味着免费匠可以在这段时间内刷 TTT 堵墙。两人一共搞定 T+1T+1T+1 堵墙。
3. 状态定义：`dp[j]` 代表搞定 jjj 堵墙的最小花费。因为我们只需要达到 nnn 堵墙，所以对于任何覆盖数大于 nnn 的方案，都直接收敛到 `dp[n]`。
4. 复杂度：时间复杂度为 O(n2)O(n2)O(n2)，空间复杂度优化后为 O(n)O(n)O(n)。
------
如果你观察一下 time 的取值范围，会发现其实还有个更有意思的推演：为什么这种“买一赠多”的逻辑可以完美等价于经典的 0-1 背包，而不是多重背包。这背后其实涉及到一个关于“时间换空间”的等价代换技巧，想听听吗？