【动态规划】【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=0i1(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;

};


目录
打赏
0
0
0
0
36
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
|
30天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
50 5
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
65 4
|
3月前
|
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
90 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等