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＜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<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];
}工夫复杂度：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<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];
}工夫复杂度：O(dn)
空间复杂度：O(n)
发表回复