【动态规划】【C++算法】1335 工作计划的最低难度

2024-02-04 04:36
文章标签 算法 动态 规划 c++ 工作 计划 最低 难度 1335

本文主要是介绍【动态规划】【C++算法】1335 工作计划的最低难度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

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。
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>(sta.top()) <= curDiff))
{
iPrePopMin = min(iPrePopMin, get<2>(sta.top()));
sta.pop();
}
int curRet = (INT_MAX ==iPrePopMin) ? INT_MAX : (curDiff+iPrePopMin);
if (sta.size())
{
curRet = min(curRet, get<1>(sta.top()));
}
dp[cur] = curRet;
sta.emplace(curDiff, curRet, iPrePopMin);
}
pre.swap(dp);
}
return (INT_MAX == pre.back()) ? -1 : pre.back();
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

这篇关于【动态规划】【C++算法】1335 工作计划的最低难度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/676357。

相关文章

C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
go动态限制并发数量的实现示例

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发，所以面试百分百会问到
阅读更多...
C++中detach的作用、使用场景及注意事项

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()？它的作用是什么？类比一下：二、join()的作用总结三、join()怎么
阅读更多...
Java中的xxl-job调度器线程池工作机制

Java中的xxl-job调度器线程池工作机制

《Java中的xxl-job调度器线程池工作机制》xxl-job通过快慢线程池分离短时与长时任务,动态降级超时任务至慢池,结合异步触发和资源隔离机制,提升高频调度的性能与稳定性,支撑高并发场景下的可靠... 目录⚙️ 一、调度器线程池的核心设计 二、线程池的工作流程 三、线程池配置参数与优化 四、总结：线程
阅读更多...
C++中全局变量和局部变量的区别

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域
阅读更多...
C++中assign函数的使用

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)
阅读更多...
c++ 类成员变量默认初始值的实现

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中，如果使用类成员变量时未给定其初始值，那么它将被
阅读更多...
C++中NULL与nullptr的区别小结

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL
阅读更多...
C++ Log4cpp跨平台日志库的使用小结

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2