1335. 工作计划的最低难度
关键词：动态规划、线性DP、单调栈
题目来源：1335. 工作计划的最低难度 – 力扣（Leetcode）
题目描述
T动态规划
T线性DP
T单调栈你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 ）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 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 动态规划
设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 &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size();
if (n = 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 &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size(), INF = 1e9;
if (n = 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＜j的最大p，则f(i, j)的求解可分为如下两部分：
- 当k≥p时，max(k+1, j) = job[j]，故f(i, j) = min( f(i-1, k) ) + job[j]，其中k∈[p, j-1]
- 当k＜p时，f(i, j) = min( f(i-1, k) + max(k+1..p) ) = f(i, p)，其中k∈[i, p-1]
维护p可使用单调栈，但同时还需要维护min( f(i-1, k) ) ，故采用二元组(p, v)，表示满足job[p]>job[j]且p＜j的最大p，且min( f(i-1, k) ) = v。
int minDifficulty_4(vector &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size();
if (n 时间复杂度：O(dn)。对于每个j，求对应p的过程可看做是O(1)的，因为每轮（对于i而言），入栈/出栈操作最多只有n次。
空间复杂度：O(dn)
在计算第i行时只用到第i-1行的数据，故也可采用滚动数组对空间进行优化，但是，不能像解法一动态规划中那样改变j的遍历顺序，因为本解法中，在计算(i, j)时，用到了(i, k)，其中k小于j，所以需要在j之前计算出k，故采用两个数组交替使用的方式。
int minDifficulty_5(vector &jobDifficulty, int d) {
auto &job = jobDifficulty;
int n = job.size();
if (n 时间复杂度：O(dn)
空间复杂度：O(n)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
