题目简介：
你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。
示例 1：
1
2
3
4
5
| 输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7
|
示例 2：
1
2
3
| 输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。
|
提示：
1 <= jobDifficulty.length <= 3000 <= jobDifficulty[i] <= 10001 <= d <= 10
思路：
一开始想的是用回溯做，可惜超时了。
然后尝试用记忆化搜索，我们定义temp[d][pos]为用d天时间完成[pos, jobDifficulty.size() - 1]工作所花费的时间。
若d = 1，则说明要完成后面所有的工作。
否则，我们枚举后一段工作的开始下标i，也就是说我们枚举用d - 1天的时间完成了[i + 1, jobDifficulty.size() - 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
38
39
40
41
42
| class Solution {
public:
int solve(vector<int>& jobDifficulty, int pos, int d, vector<vector<int>>& temp){
if(temp[d][pos] != -1)
return temp[d][pos];
if(d == 1){
for(int i = pos; i < jobDifficulty.size(); ++i){
temp[d][pos] = max(temp[d][pos], jobDifficulty[i]);
}
return temp[d][pos];
}
int res = INT_MAX;
int now_max = -1;
for(int i = pos; i < jobDifficulty.size() - d + 1; ++i){
now_max = max(now_max, jobDifficulty[i]);
res = min(res, now_max + solve(jobDifficulty, i + 1, d - 1, temp));
temp[d][pos] = res;
}
return res;
}
int minDifficulty(vector<int>& jobDifficulty, int d) {
if(jobDifficulty.size() < d)
return -1;
vector<vector<int>> temp(d + 1, vector<int>(jobDifficulty.size() + 1, -1));
return solve(jobDifficulty, 0, d, temp);
}
};
|
