题目描述：
需要制定一份 $d$ 天的工作计划表。工作之间存在依赖，要想执行第 $i$ 项工作，必须完成前面所有的工作。并且每天至少需要完成一项工作，总难度是这 $d$ 天每一天的难度之和，一天的难度是当天应该完成工作的最大难度。
给出难度数组 jobDifficulty和天数 $d$ ，返回整个工作计划的最小难度。如果无法制定工作计划，则返回 $-1$ 。
数据范围：
$1\le job.len \le 300;0\le job[i]\le 1000;1\le d \le 10$
题解：
使用动态规划解决，因为每天都必须要执行一项工作，并且一天的难度是最大值。因此本质就是将一个数组划分为 $d$ 个子数组，其中每个子数组的值都是最大值。可以枚举最后一次的划分点。使用 $dp[i][j]$ 表示 $j$ 天执行了前 $i$ 个任务，则枚举划分点时，需要找第 $j - 1$ 天的划分点 $dp[k][j-1]$ ，则可以得到
注意下标问题，这里还是使用 $[1,n]$ 作为 $dp$ 数组的下标，因此 $k\in[0, i - 1]$ 。也要注意枚举的顺序问题，因为求最大值，因此可以对 $k$ 从大到小枚举，这样的话可以方便求最大值；对 $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
27
28
29
30
31
32
33
34
35
36
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 300 + 10;
int dp[maxn][11];
int minDifficulty(vector<int> &jobDifficulty, int d)
{
int n = jobDifficulty.size();
if(n < d) return -1;
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= d; ++j)
{
int maxx = jobDifficulty[i - 1];
for (int k = i - 1; k >= 0; --k)
{
maxx = max(maxx, jobDifficulty[k]);
dp[i][j] = min(dp[i][j], dp[k][j - 1] + maxx);
}
}
}
if (dp[n][d] >= 0x3f3f3f3f)
return -1;
return dp[n][d];
}
};
|