【动态规划】【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++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
在 VSCode 中配置 C++ 开发环境的详细教程

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode（VSCode）中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境：详细教程1. 什么是 VSCode？2. 安装 VSCo
阅读更多...
如何用Python绘制简易动态圣诞树

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码：效果：总结 代码：import randomimport timefrom math
阅读更多...
Java中JSON字符串反序列化(动态泛型)

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求：定时任务扫描，反射调用目标对象，但是，方法的传参不是固定的。方案一：将方法参数存成jsON字
阅读更多...
Oracle数据库执行计划的查看与分析技巧

Oracle数据库执行计划的查看与分析技巧

《Oracle数据库执行计划的查看与分析技巧》在Oracle数据库中,执行计划能够帮助我们深入了解SQL语句在数据库内部的执行细节,进而优化查询性能、提升系统效率,执行计划是Oracle数据库优化器为... 目录一、什么是执行计划二、查看执行计划的方法（一）使用 EXPLAIN PLAN 命令（二）通过 S
阅读更多...
C++11的函数包装器std::function使用示例

C++11的函数包装器std::function使用示例

《C++11的函数包装器std::function使用示例》C++11引入的std::function是最常用的函数包装器,它可以存储任何可调用对象并提供统一的调用接口,以下是关于函数包装器的详细讲解... 目录一、std::function 的基本用法1. 基本语法二、如何使用 std::function
阅读更多...
.NET利用C#字节流动态操作Excel文件

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2