作者推荐
【动态规划】【map】【C++算法】1289. 下降路径最小和 II
本文涉及知识点
动态规划汇总
956. 最高的广告牌
你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。
返回 广告牌的最大可能安装高度 。如果没法安装广告牌,请返回 0 。
示例 1:
输入:[1,2,3,6]
输出:6
解释:我们有两个不相交的子集 {1,2,3} 和 {6},它们具有相同的和 sum = 6。
示例 2:
输入:[1,2,3,4,5,6]
输出:10
解释:我们有两个不相交的子集 {2,3,5} 和 {4,6},它们具有相同的和 sum = 10。
示例 3:
输入:[1,2]
输出:0
解释:没法安装广告牌,所以返回 0。
提示:
0 <= rods.length <= 20
1 <= rods[i] <= 1000
sum(rods[i]) <= 5000
动态规划
动态规划的状态表示
朴素方案:pre包括所有符合以下条件的元素{a
j
_j
j,b
j
_j
j},a
j
_j
j<=b
j
_j
j含义是前 i个钢筋可能组成的支架组合。可能的状态数:106。
优化方案:假设一b1-a1等于b2-a2,且a1<a2,则a1被淘汰。假定{a1,b1}能够组成的支架高度是n。则第一个剩余支架高度是:c=n-a1,第二个剩余支架高度是d=n-b1 。我们假定a2和c结果,b2和d结合,则第一个支架高度是: n-a1+a2 ,则第二个支架是:n-b1+b2。我们来证明两者相等。即 n-a1+a2
≡
\equiv
≡ n-b1+b2
→
\rightarrow
→
左右加上
a
1
+
b
1
−
n
‾
→
\underline{左右加上a1+b1-n}_\rightarrow
左右加上a1+b1−n→ b1+a2
≡
\equiv
≡a1+b2
左右减去
a
1
+
a
2
‾
→
\underline{左右减去a1+a2}_\rightarrow
左右减去a1+a2→ b1-a1
≡
\equiv
≡ b2-a2就是假设一
→
\rightarrow
→ 如果a1,b1有解,则a2,b2也有解。而a1+c<a2+c,故a1,b1被淘汰。
pre[j]表示前 i个钢筋可能组成的支架组合中,两根支架的高度差为j,短支架的最大长度。j的取值范围[0,sum(rods[i]) /2]
dp表示前i+1个钢筋的组合。
动态规划的转移方程
每个钢架有三种可能:一,不使用。二,焊在短支架上。三,焊在长支架上。
动态规划的初始状态
pre[0]=0,其它为-10000,表示非法状态。
动态规划的填表顺序
任意顺序处理钢筋。
动态规划的返回值
pre[0],如果是负数,返回0。
代码
核心代码
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
const int n = accumulate(rods.begin(), rods.end(), 0)/2;
vector<int> pre(n+1, -10000);
pre[0] = 0;
for (const auto& rod : rods)
{
auto dp = pre;//本钢筋不使用
auto Add = [&](int i1, int i2)
{
if (i2 < i1)
{
swap(i1, i2);
}
if (i2 - i1 > n)
{
return;
}
dp[i2 - i1] = max(dp[i2 - i1], i1);
};
for (int iPre = 0; iPre <= n; iPre++)
{
const int i2 = iPre + pre[iPre];
Add(pre[iPre] + rod, i2);
Add(pre[iPre], i2 + rod);
}
pre.swap(dp);
}
return max(0, pre.front());
}
};
核心代码
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> rods;
{
Solution sln;
rods = { 1, 2, 3, 6 };
auto res = sln.tallestBillboard(rods);
Assert(res,6);
}
{
Solution sln;
rods = { 1,2,3,4,5,6 };
auto res = sln.tallestBillboard(rods);
Assert(res, 10);
}
{
Solution sln;
rods = { 1,2 };
auto res = sln.tallestBillboard(rods);
Assert(res, 0);
}
}
2023年一月
class Solution {
public:
int tallestBillboard(vector& rods) {
//key: 第一个钢筋的长度- 第二根钢筋的长度, value = 第二根钢筋的长度
std::unordered_map<int, int> mPreSubLen;
mPreSubLen[0] = 0;
for (const auto& idata : rods)
{
std::unordered_map<int, int> dp = mPreSubLen;
for (const auto& pre : mPreSubLen )
{
Add(dp, pre.first + idata, pre.second);
Add(dp, pre.first - idata, pre.second + idata);
}
mPreSubLen.swap(dp);
}
return mPreSubLen[0];
}
void Add(std::unordered_map<int, int>& dp,int iSub,int iLen)
{
auto it = dp.find(iSub);
if (dp.end() == it)
{
dp[iSub] = iLen;
}
else
{
it->second = max(it->second, iLen);
}
}
};
2023年8月
class Solution {
public:
int tallestBillboard(vector& rods) {
std::unordered_map<int, int> mDiffToMin;
for (const auto& n : rods)
{
std::unordered_map<int, int> cur = mDiffToMin;
auto AddNew = [&cur](const int& iDiff, const int& iMin)
{
if ((!cur.count(iDiff)) || (iMin > cur[iDiff]))
{
cur[iDiff] = iMin;
}
};
AddNew(n, 0);
for (const auto& [pre, iMin] : mDiffToMin)
{
AddNew(pre + n, iMin);
AddNew(max(pre+iMin, n + iMin) - min(pre + iMin, n + iMin), min(pre + iMin, n + iMin));
}
cur.swap(mDiffToMin);
}
return mDiffToMin[0];
}
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。文章来源:https://www.toymoban.com/news/detail-829697.html
文章来源地址https://www.toymoban.com/news/detail-829697.html
到了这里,关于【动态规划】【C++算法】956 最高的广告牌的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!