本题是一道经典的“极小极大化”问题，又结合了动态规划的考察，难度集中于数据建模过程而非编码阶段。
原题链接如下：
LeetCode 1335 工作计划的最低难度
题目实际上要求把 n 项工作分成 d 份，保证每份至少又一项工作，而且每天工作的难度就是每份划分中的最大值，而总难度为最大值的和，最后要保证这个总难度最小。
实际有 5 个示例输入：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| Input 1:
jobDifficulty = [6,5,4,3,2,1]
d = 2
Input 2:
jobDifficulty = [9,9,9]
d = 4
Input 3:
obDifficulty = [1,1,1]
d = 3
Input 4:
jobDifficulty = [7,1,7,1,7,1]
d = 3
Input 5:
jobDifficulty = [11,111,22,222,33,333,44,444]
d = 6
|
每个输入的数据都满足如下规则：
jobDifficulty 的长度区间为 $[1, 300]$jobDifficulty 的每一项取值区间为 $[0, 1000]$d 的取值区间为 $[1, 10]$
相应的示例输出为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Output 1:
7
Output 2:
-1
Output 3:
3
Output 4:
15
Output 5:
843
|
不难看出，而如果最后一天需要完成 k 项工作，那么之前的 d - 1 天里面就要完成 n - k 项工作，和最后的结果需要的答案结构类似，是一个规模更小的子问题，可以套用动态规划的解题思路。
不妨假设 $f(i,j)$ 代表使用 $i + 1$ 天完成 $jobDifficulty[0]$ 到 $jobDifficulty[j]$ 的所有工作的最小总难度，那么就有如下的递推公式：
提示
此处使用 $i + 1$ 而不是 $i$ 是为了编码方便，毕竟数组是从 0 开始计数的，同时 $jobDifficulty[0..j]$ 区间实际有 $j + 1$ 项工作
$$
f(i,j)=\min_{k=i}^{j}{{f(i-1,k-1)+\max_{p=k}^{j}{jobDifficulty[p]}}}
$$
公式中需要注意的地方如下：
- i 必定不大于 j
- k 从 i 开始，是为了保证子问题求解时至少每天完成 1 项工作
- 以上公式前提是 i 大于 0 时成立，i 为边界值 0 时为 $f(0,j)=\max_{p=0}^{j}{jobDifficulty[p]}$
可以注意到对于 $f(i,j)$，如果在 $[0..j)$ 的区间坐标中有最大的坐标 x 使得 jobDifficulty[x] 大于 jobDifficulty[j]，而且那么我们在枚举 k 的时候有如下可能：
- 如果 $k < x$ 则区间 $jobDifficulty[k..j]$ 上的最大值是区间
jobDifficulty[k..x] 的最大值，所以 $f(i,j)=f(i,x)$ - 如果 $k \ge x$ 则区间 $jobDifficulty[k..j]$ 上的最大值就是
jobDifficulty[j]，所以 $f(i,j)=jobDifficulty[j]+\min_{p=x}^{j-1}{{f(i-1,p)}}$
第一种情况只需要知道 x 的值即可，那么只要使用单调栈即可，即维护一个存储工作下标（逐渐递增）的单调栈，保证从栈底到栈顶的下标对应的工作难度递减。
第二种情况较为复杂，为了方便对于多个 $f(i,j)$ 求解最小值的计算，单调栈的保存的数据可以更加复杂，即维护一个存储二元组 (idx, val) 的单调栈：
- 保证从栈底到栈顶的
idx 递增 - 保证从栈底到栈顶的
idx 对应的 jobDifficulty[idx] 递减 - 保证
val 就是各个 $f(i - 1,j)$ 的最小值
这样在不断枚举 j 的过程中就可以不断求解和记录 $\min_{p=x}^{j-1}{{f(i-1,p)}}$ 的各项值。
在区间 $jobDifficulty[k..j]$ 上求最大值不会增加额外的时间复杂度，具体思路是：如果我们从小到大枚举 k 的值，区间会不断减小，求最大值的操作不便实现。不如从大到小枚举 k 使得区间从 0 开始增长，比较新的 jobDifficulty[k] 就能得到新区间对应的最大值。
显然，类似背包问题中对空间复杂度的优化，本题的递推公式中 $f(i)$ 只和 $f(i-1)$ 相关，可以使用一维数组优化缓存数据，只需要倒序遍历 j 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| impl Solution {
pub fn min_difficulty(job_difficulty: Vec<i32>, d: i32) -> i32 {
let n = job_difficulty.len();
let d = d as usize;
if d > n {
return -1;
}
let mut dp = vec![0; n];
let mut mx = 0;
for i in 0..n {
mx = mx.max(job_difficulty[i]);
dp[i] = mx;
}
for i in 1..d {
for j in (i..n).rev() {
let mut mx = 0;
dp[j] = 0x3f3f3f;
for k in (i..=j).rev() {
mx = mx.max(job_difficulty[k]);
dp[j] = dp[j].min(dp[k - 1] + mx);
}
}
}
dp[n - 1]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| use std::collections::VecDeque;
impl Solution {
pub fn min_difficulty(job_difficulty: Vec<i32>, d: i32) -> i32 {
let n = job_difficulty.len();
let d = d as usize;
if d > n {
return -1;
}
let mut dp = vec![vec![0; n]; d];
let mut mx = 0;
for i in 0..n {
mx = mx.max(job_difficulty[i]);
dp[0][i] = mx;
}
for i in 1..d {
let mut stack = VecDeque::new();
for j in i..n {
let mut mn = dp[i - 1][j - 1];
while let Some((idx, val)) = stack.back() {
if job_difficulty[*idx] >= job_difficulty[j] {
break;
} else {
mn = mn.min(*val);
stack.pop_back();
}
}
dp[i][j] = mn + job_difficulty[j];
if let Some((idx, _)) = stack.back() {
dp[i][j] = dp[i][j].min(dp[i][*idx]);
}
stack.push_back((j, mn));
}
}
dp[d - 1][n - 1]
}
}
|