【动态规划】【C++算法】956 最高的广告牌

作者推荐

【动态规划】【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个钢筋可能组成的支架组合。可能的状态数：10⁶。

优化方案：假设一b1-a1等于b2-a2，且a1

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& rods) {
		const int n = accumulate(rods.begin(), rods.end(), 0)/2;
		vector 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
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& 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 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 mPreSubLen;

mPreSubLen[0] = 0;

for (const auto& idata : rods)

{

std::unordered_map 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& 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 mDiffToMin;

for (const auto& n : rods)

{

std::unordered_map 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++**实现。