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 ] ) \begin{cases} dp[min(1000,j+cost[i])] = min(,pre[j]+cost[i]) & 使用付费工人 \\ dp[j-1] = min(,pre[j]) & \\ \end{cases} {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;
};

测试用例

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

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;

};