千问 LeetCode 2742. 给墙壁刷油漆 Java实现

这道题是一道经典的动态规划问题可以转化为“01背包”模型来求解。题目核心思路分析我们需要雇佣付费油漆匠和免费油漆匠来刷完 n 堵墙目标是让总开销最小。* 付费油漆匠刷第 i 堵墙花费 cost[i]耗时 time[i]。* 免费油漆匠刷任意墙花费 0耗时 1。* 关键限制免费油漆匠必须在付费油漆匠工作时才能工作。这意味着如果我们雇佣付费油漆匠去刷第 i 堵墙他不仅完成了这 1 堵墙同时他工作的 time[i] 这段时间还可以让免费油漆匠顺手刷完 time[i] 堵其他的墙。因此雇佣付费油漆匠刷第 i 堵墙的“实际收益”是完成了 time[i] 1 堵墙1堵自己刷的 time[i]堵免费刷的。问题就转化为了一个01背包问题* 背包容量需要刷的墙的总数 n。* 物品每一堵墙都可以看作一个物品。* 物品体积雇佣付费油漆匠刷第 i 堵墙能覆盖的墙数即 time[i] 1。* 物品价值开销雇佣付费油漆匠刷第 i 堵墙的成本即 cost[i]。* 目标在覆盖至少 n 堵墙的前提下使得总开销最小。Java 动态规划实现我们可以使用一维数组来进行空间优化的动态规划滚动数组。class Solution {public int paintWalls(int[] cost, int[] time) {int n cost.length;// dp[j] 表示完成至少 j 堵墙所需的最小开销// 初始化为一个较大的值防止加法溢出可以使用 Integer.MAX_VALUE / 2int[] dp new int[n 1];java.util.Arrays.fill(dp, Integer.MAX_VALUE / 2);// 完成 0 堵墙的开销为 0dp[0] 0;// 遍历每一堵墙即遍历每一个物品for (int i 0; i n; i) {int c cost[i];// 当前付费油漆匠刷这面墙实际能覆盖的墙数体积int t time[i] 1;// 01背包倒序遍历防止同一面墙被重复计算for (int j n; j 0; j--) {// 状态转移// 1. 不雇佣付费油漆匠刷第 i 堵墙开销保持 dp[j] 不变// 2. 雇佣付费油漆匠刷第 i 堵墙开销为 dp[上一状态] c// 上一状态需要覆盖的墙数是 j - t如果 j - t 0说明这面墙足以覆盖所有剩余需求取 dp[0] 即可dp[j] Math.min(dp[j], dp[Math.max(0, j - t)] c);}}// 返回完成至少 n 堵墙的最小开销return dp[n];}}复杂度分析* 时间复杂度O(N²)其中 N 是墙的数量。我们需要遍历 N 个物品内层循环遍历容量 N。* 空间复杂度O(N)使用了一个长度为 N1 的一维 dp 数组。