广州智迅网络做网站,dw学校网站制作教程,校园app开发,深圳制作网页公司作者推荐
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
本文涉及知识点
动态规划汇总
LeetCode2742. 给墙壁刷油漆
给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time #xff0c;分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有…作者推荐
【数位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] 106 1 time[i] 500
动态规划
动态规划的状态表示
合法状态付费工人用时大于等于免费工人用时。 注意第i项工作付费工人需要time[i]时间免费工人需要1。所以前i项工作付费工人用时和免费工人用时之和不固定。 免费工人用时 ∈ \in ∈[0,500]付费工人用时大于等于500必定可行所以付费用时用时也 ∈ \in ∈[0,500]。 如果直接暴力处理空间复杂度:O(n2)处理每份工作时间复杂度O(n)总时间复杂度O(n3)超时。 状态优化 付费工人用时免费工人用时 ⟺ \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,jcost[i])] min(,pre[j]cost[i]) 使用付费工人 \\ dp[j-1] min(,pre[j]) \\ \end{cases} {dp[min(1000,jcost[i])]min(,pre[j]cost[i])dp[j−1]min(,pre[j])使用付费工人
动态规划的初始值
dp[500] 0
动态规划的填表顺序
依次处理各任务。
动态规划返回值
dp[500,1000]的最大值。
代码
核心代码
templateclass ELE,class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft,(ELE) other);
}templateclass ELE
void MaxSelf(ELE* seft, const ELE other)
{*seft max(*seft, other);
}class Solution {
public:int paintWalls(vectorint cost, vectorint time) {int n cost.size();vectorint pre(n * 2 1, m_iNotMay);pre[n] 0;for (int i 0; i cost.size(); i){vectorint 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;
};测试用例 templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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;vectorint 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_c1,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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
