本文涉及知识点
动态规划汇总
LeetCode1335. 工作计划的最低难度
你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。
示例 1：
输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7
示例 2：
输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。
示例 3：
输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3 。
示例 4：
输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15
示例 5：
输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843
提示：
1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10
动态规划
预处理
如果任务数小于天数，直接返回-1。
vHard[left][r]表示第left项任务到第r项任务的最大难道。由于vHard[left[r+1] = max(vHard[left][r]+ jobDiffficulty[r+1]) 所有预处理的时间为O(n^n)。
动态规划的状态表示
pre[j]前i天完成j项任务最小难度，dp[j]前i+1天完成j项任务最小难度。
动态规划的转移方程
d p [ i ] = M i n j = 0 i − 1 dp[i]=Min\Large_{j=0}^{i-1} dp[i]=Minj=0i−1(pre[j]+vHard[j][i-1])
动态规划的初始状态
dp[0]=0，其它全部1e6，表示非法状态。
动态规划的填表顺序
i,j 皆从小到大。
动态规划的返回值
pre.back
代码
核心代码
class Solution {
public:
int minDifficulty(vector<int>& jobDifficulty, int d) {
m_c = jobDifficulty.size();
if (m_c < d)
{
return -1;
}
vector<vector<int>> vHard(m_c, vector<int>(m_c));
for (int i = 0; i < m_c; i++)
{
vHard[i][i] = jobDifficulty[i];
for (int j = i + 1; j < m_c; j++)
{
vHard[i][j] = max(vHard[i][j - 1], jobDifficulty[j]);
}
}
vector<int> pre(m_c + 1, m_iNotMay);
pre[0] = 0;
while(d--)
{
vector<int> dp(m_c + 1, m_iNotMay);
for (int j = 1; j <= m_c; j++)
{
for (int k = 0; k < j; k++)
{
dp[j] = min(dp[j], pre[k] + vHard[k][j-1]);
}
}
pre.swap(dp);
}
return pre.back();
}
int m_c;
const int m_iNotMay = 1000'000;
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<int> jobDifficulty;
int d;
{
Solution sln;
jobDifficulty = { 6, 5, 4, 3, 2, 1 }, d = 2;
auto res = sln.minDifficulty(jobDifficulty, d);
Assert(7, res);
}
{
Solution sln;
jobDifficulty = { 9, 9, 9 }, d = 4;
auto res = sln.minDifficulty(jobDifficulty, d);
Assert(-1, res);
}
{
Solution sln;
jobDifficulty = { 1, 1, 1 }, d = 3;
auto res = sln.minDifficulty(jobDifficulty, d);
Assert(3, res);
}
{
Solution sln;
jobDifficulty = { 7, 1, 7, 1, 7, 1 }, d = 3;
auto res = sln.minDifficulty(jobDifficulty, d);
Assert(15, res);
}
{
Solution sln;
jobDifficulty = { 11, 111, 22, 222, 33, 333, 44, 444 }, d = 6;
auto res = sln.minDifficulty(jobDifficulty, d);
Assert(843, res);
}
}
2023年2月 第一版
class Solution {
public:
int minDifficulty(vector& jobDifficulty, int d) {
std::unordered_map<int, std::unordered_map<int, int>> mDayMaxJobIndexs;
mDayMaxJobIndexs[1][0] = jobDifficulty[0];
for (int i = 1; i < jobDifficulty.size(); i++)
{
std::unordered_map<int, std::unordered_map<int, int>> dp;
for (const auto& it : mDayMaxJobIndexs)
{
const int& iDay = it.first;
for (const auto& ij : it.second)
{
const int& iMaxJobIndex = ij.first;
const int& iValue = ij.second;
if (jobDifficulty[i] > jobDifficulty[iMaxJobIndex])
{
Test(dp, iDay, i, iValue + jobDifficulty[i] - jobDifficulty[iMaxJobIndex] );
}
else
{
Test(dp, iDay, iMaxJobIndex, iValue);
}
if (iDay < d)
{
Test(dp, iDay + 1, i, iValue + jobDifficulty[i]);
}
}
}
dp.swap(mDayMaxJobIndexs);
}
auto it = mDayMaxJobIndexs.find(d);
if (mDayMaxJobIndexs.end() == it)
{
return -1;
}
int iMin = INT_MAX;
for (const auto& ij : it->second)
{
iMin = min(iMin, ij.second);
}
return iMin;
}
void Test(std::unordered_map<int, std::unordered_map<int, int>>& dp, int iDay, int iMaxJobIndex, int iValue )
{
auto it = dp[iDay].find(iMaxJobIndex);
if (dp[iDay].end() == it)
{
dp[iDay][iMaxJobIndex] = iValue;
}
else
{
it->second = min(it->second, iValue);
}
}
};
2023年8月版
class Solution {
public:
int minDifficulty(vector& jobDifficulty, int d) {
m_c = jobDifficulty.size();
vector<vector> vMax(m_c, vector(m_c)); //vMax[i][i]表示[i,j]的最大值
for (int left = m_c - 1; left >= 0; left–)
{
vMax[left][left] = jobDifficulty[left];
for (int r = m_c-1 ; r > left; r–)
{
vMax[left][r] = max(jobDifficulty[left], vMax[left + 1][r]);
}
}
vector pre(m_c + 1, INT_MAX);//pre[i]表示已经处理了i项的最小难度
pre[0] = 0;
for (int i = 0; i < d; i++)
{
vector dp(m_c + 1, INT_MAX);
for (int cur = i + 1; cur <= m_c; cur++)
{
for (int pr = 0; pr < cur; pr++)
{
if (INT_MAX == pre[pr])
{
continue;
}
dp[cur] = min(dp[cur], pre[pr] + vMax[pr][cur - 1]);
}
}
pre.swap(dp);
}
return (INT_MAX == pre.back()) ? -1 : pre.back();
}
int m_c;
};
2023年8月 第二版
class Solution {
public:
int minDifficulty(vector& jobDifficulty, int d) {
m_c = jobDifficulty.size();
if (m_c < d)
{
return -1;
}
vector<vector> vMax(m_c, vector(m_c)); //vMax[i][i]表示[i,j]的最大值
for (int left = m_c - 1; left >= 0; left–)
{
vMax[left][left] = jobDifficulty[left];
for (int r = m_c-1 ; r > left; r–)
{
vMax[left][r] = max(jobDifficulty[left], vMax[left + 1][r]);
}
}
vector pre(m_c , INT_MAX);//pre[i]表示已经处理了i项的最小难度
for (int i = 0; i < d; i++)
{
vector dp(m_c , INT_MAX);
std::stack<std::tuple<int, int, int>> sta;//工作难度 dp[0]到当前的最小难度 被pop的pre最小难度
if (i > 0)
{
dp[i] = jobDifficulty[i] + pre[i - 1];
sta.emplace(jobDifficulty[i], dp[i], pre[i -1]);
}
else
{
dp[i] = jobDifficulty[i];
sta.emplace(jobDifficulty[i], dp[i], 0);
}
for (int cur = i+1; cur < m_c; cur++)
{
const int& curDiff = jobDifficulty[cur];
int iPrePopMin = pre[cur - 1];
while (sta.size() && (get<0>(()) <= curDiff))
{
iPrePopMin = min(iPrePopMin, get<2>(()));
sta.pop();
}
int curRet = (INT_MAX ==iPrePopMin) ? INT_MAX : (curDiff+iPrePopMin);
if (sta.size())
{
curRet = min(curRet, get<1>(()));
}
dp[cur] = curRet;
sta.emplace(curDiff, curRet, iPrePopMin);
}
pre.swap(dp);
}
return (INT_MAX == pre.back()) ? -1 : pre.back();
}
int m_c;
};
