算法leetcode

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

字数统计: 2k字   |   阅读时长: 8分
, ,

摘要: 非常综合的搜索题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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 这些钢筋的选取，使得 lh 和 rh 分别为 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 时，如果没被剪枝掉，则再查一下备忘录，如果之前没搜过，才继续搜索下去，否则之前已经搜索过并且在答案中更新了，直接返回。

等效性剪枝

lh 和 rh 如果互换，则对搜索结果无影响，也应该视为重复子问题，因此以下 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，只需要将 rh 和 lh 交换再搜索，而 dfs(rh, lh, i) 此前可能搜索过，这样就减少了对 dfs(lh, rh, i) 的搜索，可以理解为一种等效性剪枝。

状态取值稀疏

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

而考虑到 lh 和 rh 的稀疏性，也就是整个搜索过程中，lh 和 rh 的取值均只会取到 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