这道题的核心是将其转化为0-1 背包问题。每当付费油漆匠工作 time[i]time[i]time[i] 时间他不仅刷完了一堵墙还额外赠送了免费油漆匠刷 time[i]time[i]time[i] 堵墙的时间。因此雇佣第 iii 个工匠的实际贡献是覆盖了 1time[i]1 time[i]1time[i] 堵墙。我们的目标是从 nnn 堵墙中选出若干项目使得它们的总覆盖数 ∑(1time[i])≥n\sum (1 time[i]) \ge n∑(1time[i])≥n且总 cost 最小。TypeScript 实现【typescript】function paintWalls(cost: number[], time: number[]): number {const n cost.length;// dp[j] 表示覆盖 j 堵墙所需的最小开销// 初始化为最大值dp[0] 为 0const 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 堵墙。两人一共搞定 T1T1T1 堵墙。3. 状态定义dp[j] 代表搞定 jjj 堵墙的最小花费。因为我们只需要达到 nnn 堵墙所以对于任何覆盖数大于 nnn 的方案都直接收敛到 dp[n]。4. 复杂度时间复杂度为 O(n2)O(n2)O(n2)空间复杂度优化后为 O(n)O(n)O(n)。------如果你观察一下 time 的取值范围会发现其实还有个更有意思的推演为什么这种“买一赠多”的逻辑可以完美等价于经典的 0-1 背包而不是多重背包。这背后其实涉及到一个关于“时间换空间”的等价代换技巧想听听吗