【动态规划】【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。

相关文章

Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
SpringBoot整合Flowable实现工作流的详细流程

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
LiteFlow轻量级工作流引擎使用示例详解

LiteFlow轻量级工作流引擎使用示例详解

《LiteFlow轻量级工作流引擎使用示例详解》：本文主要介绍LiteFlow是一个灵活、简洁且轻量的工作流引擎,适合用于中小型项目和微服务架构中的流程编排,本文给大家介绍LiteFlow轻量级工... 目录1. LiteFlow 主要特点2. 工作流定义方式3. LiteFlow 流程示例4. LiteF
阅读更多...
SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程

《SpringBoot集成LiteFlow实现轻量级工作流引擎的详细过程》LiteFlow是一款专注于逻辑驱动流程编排的轻量级框架,它以组件化方式快速构建和执行业务流程,有效解耦复杂业务逻辑,下面给大... 目录一、基础概念1.1 组件（Component）1.2 规则（Rule）1.3 上下文（Conte
阅读更多...
C++作用域和标识符查找规则详解

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域（Scope）和标识符查找（IdentifierLookup）是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找（Ordinary Lookup）2. 限定查找（Qualif
阅读更多...
Java调用C#动态库的三种方法详解

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们... 目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2