作者推荐
【数位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)超时。
状态优化
付费工人用时>=免费工人用时 ⟺ \iff ⟺ 付费工人用时 - 免费工人用时 >=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;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。