【动态规划】【C++算法】2742. 给墙壁刷油漆

作者推荐

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

本文涉及知识点

动态规划汇总

LeetCode2742. 给墙壁刷油漆

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：
一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少。
示例 1：
输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。
示例 2：
输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。
提示：
1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 10⁶
1 <= time[i] <= 500

动态规划

动态规划的状态表示

合法状态：付费工人用时大于等于免费工人用时。
注意：第i项工作，付费工人需要time[i]时间，免费工人需要1。所以前i项工作，付费工人用时和免费工人用时之和不固定。
免费工人用时$\in$[0,500]，付费工人用时大于等于500，必定可行，所以付费用时用时也$\in$[0,500]。
如果直接暴力处理，空间复杂度:O(n²)，处理每份工作时间复杂度O(n)，总时间复杂度O(n³)超时。
状态优化
付费工人用时>=免费工人用时 $⟺$ 付费工人用时 - 免费工人用时 >=0
付费工人用时 - 免费工人用时$\in$[-500,500] 为了方便可以加上500，变成$\in$[0,100don0]
空间复杂度变成：O(n) 总时间复杂度：O(nn)。

动态规划的转移方程

{ d p [ m i n ( 1000 , j + c o s t [ i ] ) ] = m i n ( , p r e [ j ] + c o s t [ i ] ) 使用付费工人 d p [ j − 1 ] = m i n ( , p r e [ j ] ) {dp[min(1000,j+cost[i])]=min(,pre[j]+cost[i])使用付费工人dp[j−1]=min(,pre[j])

{dp[min(1000,j+cost[i])]=min(,pre[j]+cost[i])dp[j−1]=min(,pre[j])​使用付费工人​

动态规划的初始值

dp[500]= 0

动态规划的填表顺序

依次处理各任务。

动态规划返回值

dp[500,1000]的最大值。

代码

核心代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
	*seft = min(*seft,(ELE) other);
}

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}

class Solution {
public:
	int paintWalls(vector<int>& cost, vector<int>& time) {
		int n = cost.size();
		vector<int> pre(n * 2 + 1, m_iNotMay);
		pre[n] = 0;
		for (int i = 0; i < cost.size(); i++)
		{
			vector<int> dp(n * 2 + 1, m_iNotMay);
			for (int j = 0; j <= n * 2; j++)
			{
				if (pre[j] >= m_iNotMay)
				{
					continue;
				}
				MinSelf(&dp[min(2 * n, j + time[i])], pre[j] + cost[i]);
				MinSelf(&dp[j - 1], pre[j]);
			}
			pre.swap(dp);
		}
		return *std::min_element(pre.begin() + n, pre.end());
	}
	const int m_iNotMay = 1e9;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& 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()
{	
	int n;
	vector<int> cost,  time;
	{
		Solution sln;
		cost = { 1, 2, 3, 2 }, time = { 1, 2, 3, 2 };
		auto res = sln.paintWalls(cost, time);
		Assert(res,3);
	}

	{
		Solution sln;
		cost = { 2, 3, 4, 2 }, time = { 1, 1, 1, 1 };
		auto res = sln.paintWalls(cost, time);
		Assert(res, 4);
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2023年6月

class Solution {
public:
int paintWalls(vector& cost, vector& time) {
m_c = cost.size();
vector< int> preTimeAddNumToMinCost(m_c+1,INT_MAX);
preTimeAddNumToMinCost[0] = 0;
for (int ii = 0; ii < m_c; ii++)
{
vector< int> dp = preTimeAddNumToMinCost;
for (int j = 0; j < m_c; j++ )
{
if (INT_MAX == preTimeAddNumToMinCost[j])
{
continue;
}
int iTimeAndNum = j + time[ii] + 1 ;
const int iCurCost = preTimeAddNumToMinCost[j] + cost[ii];
iTimeAndNum = min(iTimeAndNum, m_c);
dp[iTimeAndNum] = min(dp[iTimeAndNum], iCurCost);
}
dp.swap(preTimeAddNumToMinCost);
}
return preTimeAddNumToMinCost[m_c];
}
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++**实现。