当前位置：首页 > news >正文

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

news 2026/8/22 7:04:24

这是 LeetCode 第 1335 题《工作计划的最低难度》，核心是将工作任务分配到 `d` 天中，使得总难度（每天完成工作的最大难度之和）最小。以下是基于 **动态规划** 的最优解决方案：

---

## 一、问题核心规则
1. **输入**：工作难度数组 `jobDifficulty` 和天数 `d`
2. **约束**：工作必须按顺序完成，每天至少完成一项工作
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`，可以动态维护区间最大值

---

## 三、完整可运行代码
```java
class 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：示例1
int[] jobDifficulty1 = {6,5,4,3,2,1};
System.out.println(new Solution().minDifficulty(jobDifficulty1, 2)); // 输出: 7（第一天完成前5项，难度6；第二天完成最后1项，难度1）

// 测试用例2：示例2
int[] jobDifficulty2 = {9,9,9};
System.out.println(new Solution().minDifficulty(jobDifficulty2, 4)); // 输出: -1（工作总数3 < 天数4，无法分配）

// 测试用例3：示例3
int[] jobDifficulty3 = {1,1,1};
System.out.println(new Solution().minDifficulty(jobDifficulty3, 3)); // 输出: 3（每天完成1项，总难度1+1+1=3）

// 测试用例4：示例4
int[] jobDifficulty4 = {7,1,7,1,7,1};
System.out.println(new Solution().minDifficulty(jobDifficulty4, 3)); // 输出: 15（分配为[7,1,7], [1,7], [1]，难度7+7+1=15）
```

---

## 七、关键优化点
### 1. 动态维护区间最大值
倒序遍历 `k` 时，动态维护 `currentMax`，避免重复计算区间最大值，将时间复杂度从 O(d*n²) 优化为 O(d*n²)（常数级优化）

### 2. 空间优化
可以使用一维数组代替二维数组，只保留前一天的状态，将空间复杂度从 O(d*n) 优化为 O(n)

```java
class 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];
}
}
```