【搜索难题】力扣956-最高的广告牌

  |  

摘要: 非常综合的搜索题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个综合性很强的搜索问题,会遇到搜索中的多种优化方法,首先比较关键的是找到剪枝方法,本题最终通过适当维护变量进行可行性剪枝和最优性剪枝,非常 work;其次为了尽早剪枝,搜索顺序需要改变;然后在搜索过程中会遇到重复子问题,通过哈希表记录当前的参数此前是否搜索过。

前面的搜索优化到最后,会发现是一个记忆化搜索,因此本题也可以优化一下状态表示,然后用动态规划解决。

$1 题目

956. 最高的广告牌

你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。

返回广告牌的最大可能安装高度。如果没法安装广告牌,请返回 0。

提示:

1
2
3
0 <= rods.length <= 20
1 <= rods[i] <= 1000
钢筋的长度总和最多为 5000

示例 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。

$2 题解

算法1: 搜索

  • 基本搜索:考虑前 $i$ 根,有的放左,有的放右,有的不选,每一根有三种可能的处理方式。
  • 搜索时维护左边高度 $l_{h}$,右边高度 $r_{h}$。

剪枝

额外维护一个 remain,记录剩余的钢筋的长度之和。

可行性剪枝

如果剩余长度已经不够覆盖差值,那么即使全都取上也不能能形成合法的广告牌高度。则不用再继续搜索了。

1
2
if(abs(lh - rh) > remain)
return;

最优性剪枝

剩余的长度即使全都用上,可能形成的最高高度,也不会比之前取得过的最高高度更高,则不用再继续搜索了。

1
2
if(lh + rh + remain <= ans * 2)
return;

实践中这些剪枝非常 work。

搜索顺序

为了尽早剪枝,应该让较长的钢筋先搜索。

记忆化搜索

这样在搜索过程中,对于当前的状态 $l_{h}, r_{h}, i$ 来说,可能会遇到很多重复情况,例如 rods 如下:

1
[102,101,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100]

这样考虑 i = 4 的情况,0 ~ 3 这些钢筋的选取,使得 lhrh 分别为 202 和 201 的情况有以下 2 种,也就是说会搜索两次 dfs(202, 201, 4)

1
2
3
4
5
6
(1)
lh = rods[0] + rods[2]
rh = rods[1] + rods[3]
(2)
lh = rods[0] + rods[3]
rh = rods[1] + rods[2]

当 $i$ 继续变大的时候,重复子问题更多。因此需要考虑记忆化搜索,备忘录为 dp[i][lh][rh],是一个布尔值,表示 (i, lh, rh) 之前是否已经搜索过了。

这样如果搜索到状态 i, lh, rh 时,如果没被剪枝掉,则再查一下备忘录,如果之前没搜过,才继续搜索下去,否则之前已经搜索过并且在答案中更新了,直接返回。

等效性剪枝

lhrh 如果互换,则对搜索结果无影响,也应该视为重复子问题,因此以下 lh=201, rh=202 与前面的两种情况是重复的。

1
2
3
4
5
6
(3)
lh = rods[1] + rods[2]
rh = rods[0] + rods[3]
(4)
lh = rods[1] + rods[3]
rh = rods[0] + rods[2]

也就是说如果之前搜索过 dfs(202, 201, 4),就相当于已经搜索过 dfs(201, 202, 4)

因此在搜索中 dfs(lh, rh, i) 只需要考虑 lh > rh 的情况即可。如果 lh < rh,只需要将 rhlh 交换再搜索,而 dfs(rh, lh, i) 此前可能搜索过,这样就减少了对 dfs(lh, rh, i) 的搜索,可以理解为一种等效性剪枝。

状态取值稀疏

另外注意到数据限制里面长度总和不超过 5000,因此 lhrh 这两个维度的取值范围均为 0 ~ 2500,但是 i 的取值范围也有 0 ~ 20,如果把空间都开出来,需要 2500 * 2500 * 20,空间超了。

而考虑到 lhrh 的稀疏性,也就是整个搜索过程中,lhrh 的取值均只会取到 0 ~ 2500 的一部分,因此可以用哈希表来维护,这也是状态的某一维度取值稀疏时的处理方法。

1
vector<unordered_map<int, unordered_set<int>>> dp;

dp[i][lh].count(rh) > 0,则说明 dfs(lh, rh, i) 之前搜索过。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
int n = rods.size();
if(n < 2)
return 0;
// 用于剪枝的变量
int remain = 0;
for(int i: rods)
remain += i;
// 搜索顺序
sort(rods.begin(), rods.end(), greater<int>());
// 记忆化搜索
dp = vector<unordered_map<int, unordered_set<int>>>(n);
int ans = 0;
dfs(0, 0, 0, remain, ans, rods);
return ans;
}

private:
vector<unordered_map<int, unordered_set<int>>> dp;

void dfs(int lh, int rh, int i, int remain, int& ans, const vector<int>& rods)
{
int n = rods.size();
if(lh == rh)
ans = max(ans, lh);
if(i == n)
return;
// 可行性剪枝
if(abs(lh - rh) > remain)
return;
// 最优性剪枝
if(lh + rh + remain <= ans * 2)
return;
// 等效性剪枝
if(lh < rh)
{
dfs(rh, lh, i, remain, ans, rods);
return;
}
// 记忆化
if(dp[i].count(lh) > 0 && dp[i][lh].count(rh) > 0)
return;

dfs(lh + rods[i], rh, i + 1, remain - rods[i], ans, rods);
dfs(lh, rh + rods[i], i + 1, remain - rods[i], ans, rods);
dfs(lh, rh, i + 1, remain - rods[i], ans, rods);
dp[i][lh].insert(rh);
}
};

算法2: 动态规划

用左高和右高维护状态信息,改为用高度差和公共高度维护状态信息。

注意状态转移方程考虑“当前的状态会影响哪些状态”,而不是更常见的“哪些状态会影响当前状态”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
状态定义:
dp[i][s] := [0...i] 中,当组成的左右高度差为 s 时,左右的最大公共高度

状态转移:
(1) rods[i] 用,且放在较高一侧
dp[i][s + rods[i]] = max(dp[i][s + rods[i]], dp[i - 1][s]);
(2) rods[i] 用,且放在较矮一侧
dp[i][abs(s - rods[i])] = max(dp[i][abs(s - rods[i])], dp[i - 1][s] + min(s, rods[i]));
(3) rods[i] 不用
dp[i][s] = max(dp[i][s], dp[i - 1][s]);

初始化
dp[i][s] = -INF
dp[0][0] = 0

答案
dp[n][0]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
int n = rods.size();
if(n < 2) return 0;
int max_sum = 0;
for(int i: rods) max_sum += i;
vector<vector<int>> dp(n + 1, vector<int>(max_sum + 1, INT_MIN));
dp[0][0] = 0;
int sum = 0;
for(int i = 1; i <= n; ++i)
{
int h = rods[i - 1];
sum += h;
for(int j = 0; j <= max_sum; ++j)
{
// h 未选
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
// h 放长
if(j + h < max_sum)
dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j]);
// h 放短
dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(j, h));
}
}
return dp[n][0];
}
};

Share