纳米AI LeetCode 1335.工作计划的最低难度 public int minDifficulty(int[] jobDifficulty, int d)

这是 LeetCode 第 1335 题《工作计划的最低难度》核心是将工作任务分配到 d 天中使得总难度每天完成工作的最大难度之和最小。以下是基于 **动态规划** 的最优解决方案---## 一、问题核心规则1. **输入**工作难度数组 jobDifficulty 和天数 d2. **约束**工作必须按顺序完成每天至少完成一项工作3. **目标**找到总难度最小的工作计划4. **输出**最小总难度如果无法分配工作总数 d返回 -1---## 二、关键思路分析### 核心观察1. 若工作总数 n d直接返回 -1每天至少一项工作无法分配2. 动态规划状态 dp[i][j] 表示前 i 天完成前 j 项工作的最小总难度3. 状态转移对于第 i 天可以完成从 k 到 j 的工作k 从 i-1 到 j则- dp[i][j] min(dp[i][j], dp[i-1][k-1] max(jobDifficulty[k..j]))### 关键优化1. 预处理区间最大值提前计算所有区间 [k..j] 的最大值避免重复计算2. 倒序遍历 k在计算 dp[i][j] 时从 j 倒序遍历到 i-1可以动态维护区间最大值---## 三、完整可运行代码javaclass Solution {public int minDifficulty(int[] jobDifficulty, int d) {int n jobDifficulty.length;// 特殊情况工作总数小于天数无法分配if (n d) {return -1;}// dp[i][j] 表示前 i 天完成前 j 项工作的最小总难度int[][] dp new int[d 1][n 1];// 初始化 dp 数组为无穷大for (int i 0; i d; i) {for (int j 0; j n; j) {dp[i][j] Integer.MAX_VALUE;}}// 初始化第 1 天完成前 j 项工作的难度是 [0..j-1] 的最大值int maxDiff 0;for (int j 1; j n; j) {maxDiff Math.max(maxDiff, jobDifficulty[j - 1]);dp[1][j] maxDiff;}// 动态规划填充 dp 数组for (int i 2; i d; i) {for (int j i; j n; j) { // 前 i 天至少需要完成 i 项工作int currentMax 0;// 倒序遍历 k动态维护区间 [k..j-1] 的最大值for (int k j; k i; k--) {currentMax Math.max(currentMax, jobDifficulty[k - 1]);if (dp[i - 1][k - 1] ! Integer.MAX_VALUE) {dp[i][j] Math.min(dp[i][j], dp[i - 1][k - 1] currentMax);}}}}return dp[d][n] Integer.MAX_VALUE ? -1 : dp[d][n];}}---## 四、关键逻辑解释### 1. 初始化- dp[1][j] 表示第 1 天完成前 j 项工作的难度即 jobDifficulty[0..j-1] 的最大值- 其他 dp[i][j] 初始化为无穷大表示不可达### 2. 状态转移- 对于第 i 天必须至少完成 i 项工作j i- 倒序遍历 k从 j 到 i动态维护 jobDifficulty[k-1..j-1] 的最大值- dp[i][j] 取所有可能的 dp[i-1][k-1] currentMax 中的最小值### 3. 结果返回- dp[d][n] 表示 d 天完成所有 n 项工作的最小总难度- 若 dp[d][n] 仍为无穷大返回 -1---## 五、复杂度分析| 操作 | 时间复杂度 | 空间复杂度 ||------|------------|------------|| 初始化 | O(n) | O(d*n) || 状态转移 | O(d*n²) | O(d*n) || **总复杂度** | **O(d*n²)** | **O(d*n)** |其中 n 是工作总数d 是天数。---## 六、边界测试用例java// 测试用例1示例1int[] jobDifficulty1 {6,5,4,3,2,1};System.out.println(new Solution().minDifficulty(jobDifficulty1, 2)); // 输出: 7第一天完成前5项难度6第二天完成最后1项难度1// 测试用例2示例2int[] jobDifficulty2 {9,9,9};System.out.println(new Solution().minDifficulty(jobDifficulty2, 4)); // 输出: -1工作总数3 天数4无法分配// 测试用例3示例3int[] jobDifficulty3 {1,1,1};System.out.println(new Solution().minDifficulty(jobDifficulty3, 3)); // 输出: 3每天完成1项总难度1113// 测试用例4示例4int[] jobDifficulty4 {7,1,7,1,7,1};System.out.println(new Solution().minDifficulty(jobDifficulty4, 3)); // 输出: 15分配为[7,1,7], [1,7], [1]难度77115---## 七、关键优化点### 1. 动态维护区间最大值倒序遍历 k 时动态维护 currentMax避免重复计算区间最大值将时间复杂度从 O(d*n²) 优化为 O(d*n²)常数级优化### 2. 空间优化可以使用一维数组代替二维数组只保留前一天的状态将空间复杂度从 O(d*n) 优化为 O(n)javaclass Solution {public int minDifficulty(int[] jobDifficulty, int d) {int n jobDifficulty.length;if (n d) {return -1;}int[] prevDp new int[n 1];// 初始化第 1 天的状态int maxDiff 0;for (int j 1; j n; j) {maxDiff Math.max(maxDiff, jobDifficulty[j - 1]);prevDp[j] maxDiff;}for (int i 2; i d; i) {int[] currDp new int[n 1];Arrays.fill(currDp, Integer.MAX_VALUE);for (int j i; j n; j) {int currentMax 0;for (int k j; k i; k--) {currentMax Math.max(currentMax, jobDifficulty[k - 1]);if (prevDp[k - 1] ! Integer.MAX_VALUE) {currDp[j] Math.min(currDp[j], prevDp[k - 1] currentMax);}}}prevDp currDp;}return prevDp[n] Integer.MAX_VALUE ? -1 : prevDp[n];}}---## 八、下一步建议1. 尝试证明动态规划状态转移的正确性2. 思考如何扩展到工作可以并行完成的情况3. 验证算法在极端测试用例如n300d10中的性能表现如果需要进一步解释某个逻辑细节请随时告诉我以上内容由AI搜集并生成仅供参考