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

本文介绍: 你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0

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

你需要制定一份 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项任务最小难度。

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);
	}
}

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