共计 3182 个字符，预计需要花费 8 分钟才能阅读完成。
1335. 工作打算的最低难度
关键词：动静布局、线性 DP、枯燥栈
题目起源：1335. 工作打算的最低难度 – 力扣（Leetcode）
题目形容
T 动静布局
T 线性 DP
T 枯燥栈你须要制订一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须实现全副 j 项工作（0 <= j < i）。
你每天 至多 须要实现一项工作。工作打算的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该实现工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，别离代表工作难度和须要打算的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作打算的 最小难度。如果无奈制订工作打算，则返回 -1。
输出：jobDifficulty = [6,5,4,3,2,1], d = 2
输入：7 输出：jobDifficulty = [9,9,9], d = 4
输入：-1数据范畴
1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10动静布局
设 f(i, j) = 前 i 天实现前 j 项工作的最小难度，则 f(i, j) = min(f(i-1, k) + max(k+1..j) )，其中，k≥i（每天必须实现 1 项工作），max(k+1..j)示意工作 k +1~j 的最大难度。
int minDifficulty(vector<int> &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size();
if (n < d)return -1;
// 留神下标：代码中的天数和工作的下标均从 0 算起
int dp[d][n];
memset(dp, 0x3f, sizeof dp);
// 初始化边界
int ma = 0;
for (int i = 0; i < n; i++)
ma = max(job[i], ma), dp[0][i] = ma;
// dp
for (int i = 1; i < d; i++) {for (int j = i; j < n; j++) {
ma = 0;
for (int k = j; k >= i; k--) {ma = max(job[k], ma);
dp[i][j] = min(dp[i - 1][k - 1] + ma, dp[i][j]);
}
}
}
return dp[d - 1][n - 1];
}工夫复杂度：O(dn2)
空间复杂度：O(dn)
察看代码发现，在计算 (i,j) 时，只用到第 i - 1 行第 j 列左侧的数据，故，可 dp 数组改为一维。因为在计算 j 时用到的 k - 1 小于 j，所以，为防止计算 (i, j) 时笼罩掉计算 (i, j+1) 所须要的第 i - 1 行的数据，j 应改为从大到小。
int minDifficulty(vector<int> &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size(), INF = 1e9;
if (n < d)return -1;
// 留神下标：代码中的天数和工作的下标均从 0 算起
int dp[n];
memset(dp, 0x3f, sizeof dp);
// 初始化边界
int ma = 0;
for (int i = 0; i < n; i++)
ma = max(job[i], ma), dp[i] = ma;
// dp
for (int i = 1; i < d; i++) {for (int j = n - 1; j >= i; j--) {dp[j] = INF, ma = 0;
for (int k = j; k >= i; k--) {ma = max(job[k], ma);
dp[j] = min(dp[k - 1] + ma, dp[j]);
}
}
}
return dp[n - 1];
}工夫复杂度：O(dn2)
空间复杂度：O(n)
枯燥栈
本解法实际上是应用枯燥栈对动静布局解法进行优化，而不是单纯的枯燥栈。
对于前 j 份工作，若已知满足 job[p]>job[j]且 p
保护 p 可应用枯燥栈，但同时还须要保护 min(f(i-1, k) )，故采纳二元组 (p, v)，示意满足 job[p]>job[j] 且 p 工夫复杂度：O(dn)。对于每个 j，求对应 p 的过程可看做是 O(1)的，因为每轮（对于 i 而言），入栈 / 出栈操作最多只有 n 次。 空间复杂度：O(dn) 在计算第 i 行时只用到第 i - 1 行的数据，故也可采纳滚动数组对空间进行优化，然而，不能像解法一动静布局中那样扭转 j 的遍历程序，因为本解法中，在计算 (i, j) 时，用到了(i, k)，其中 k 小于 j，所以须要在 j 之前计算出 k，故采纳两个数组交替应用的形式。 工夫复杂度：O(dn) 空间复杂度：O(n)
int minDifficulty_4(vector<int> &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size();
if (n < d)return -1;
// 留神下标：代码中的天数和工作的下标均从 0 算起
int dp[d][n];
memset(dp, 0x3f, sizeof dp);
// 初始化边界
for (int i = 0, ma = 0; i < n; i++)
ma = max(job[i], ma), dp[0][i] = ma;
// 数组模仿枯燥栈
int stk[n][2], top; // top 指向栈顶元素
for (int i = 1, mi; i < d; i++) {
top = -1;
for (int j = i; j < n; j++) {mi = dp[i - 1][j - 1];
// 退栈，直到 job[top]>job[j]，mi 记录 dp[top+1, j-1]的最小值
while (~top && job[stk[top][0]] < job[j])
mi = min(stk[top--][1], mi);
dp[i][j] = mi + job[j];
// 栈不为空（即存在 p，有 job[p]>job[j]）if (~top)
dp[i][j] = min(dp[i][stk[top][0]], dp[i][j]);
// 以后二元组入栈
top++;
stk[top][0] = j, stk[top][1] = mi;
}
}
return dp[d - 1][n - 1];
}int minDifficulty_5(vector<int> &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size();
if (n < d)return -1;
// 留神下标：代码中的天数和工作的下标均从 0 算起
int dp[2][n], w = 0, v = 1;
memset(dp, 0x3f, sizeof dp);
// 初始化边界
for (int i = 0, ma = 0; i < n; i++)
ma = max(job[i], ma), dp[w][i] = ma;
// 数组模仿枯燥栈
int stk[n][2], top; // top 指向栈顶元素
for (int i = 1, mi; i < d; i++) {
top = -1;
for (int j = i; j < n; j++) {mi = dp[w][j - 1];
// 退栈，直到 job[top]>job[j]，mi 记录 dp[top+1, j-1]的最小值
while (~top && job[stk[top][0]] < job[j])
mi = min(stk[top--][1], mi);
dp[v][j] = mi + job[j];
// 栈不为空（即存在 p，有 job[p]>job[j]）if (~top)
dp[v][j] = min(dp[v][stk[top][0]], dp[v][j]);
// 以后二元组入栈
top++;
stk[top][0] = j, stk[top][1] = mi;
}
w = !w, v = !v; // 切换数组
}
return dp[w][n - 1];
}
