【动态规划】【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#如何动态创建Label,及动态label事件

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》：本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点：switch中的生成我们的label事件接着，
阅读更多...
SpringCloud动态配置注解@RefreshScope与@Component的深度解析

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.
阅读更多...
MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL？1.2 动态SQL的优点1.3 动态S
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
C++ 中的 if-constexpr语法和作用

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if（staticif）,：本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
C++中::SHCreateDirectoryEx函数使用方法

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1：创建单层目录示例 2：创建多级目录3. 关键注
阅读更多...
C++从序列容器中删除元素的四种方法

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque
阅读更多...
C++常见容器获取头元素的方法大全

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素（即第一个元素）是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa
阅读更多...
C++字符串提取和分割的多种方法

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2