05 August 2008
制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。
DP
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
class Solution {
// 题目的意思是 将一个数组分为 d 堆，并取出每堆中最大值，求和，并返回这些和的最小值
public int minDifficulty(int[] jobDifficulty, int d) {
int len = jobDifficulty.length;
if (len < d) return -1;
int[][] dp = new int[len][len];
int[][] ans = new int[d][len];
for (int i = 0; i < d; i++) Arrays.fill(ans[i], Integer.MAX_VALUE);
// 每种可能堆的 最大值
// dp[i][j] 为 Max(jobDifficulty[k]) = Max(dp[i][j-1], jobDifficulty[j]) 其中 i <= k <= j
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if (i == j) dp[i][j] = jobDifficulty[j];
else dp[i][j] = Math.max(dp[i][j - 1], jobDifficulty[j]);
}
}
// 初始化分堆数组
if (len - d + 1 >= 0) {
System.arraycopy(dp[0], 0, ans[0], 0, len - d + 1);
}
// 这里 i 从 0 开始
// 第i堆 分到 第j个 值时，前i堆的最小值
// ans[i][j] 表示 第 i 天分配到 第 j 个 工作的总困难度的最小值
for (int i = 1; i < d; i++) {
for (int j = i; j <= len - (d - i); j++) {
for (int k = i - 1; k <= j - 1; k++) {
// <第 i-1 天分配到 k 的最小值> 加上 <第 k+1 到 j 的工作最大值>, 与 <当前最小 ans[i][j]> 相比
ans[i][j] = Math.min(ans[i - 1][k] + dp[k + 1][j], ans[i][j]);
}
}
}
return ans[d - 1][len - 1];
}
}