摘要: 非常综合的搜索题
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
本文我们看一个综合性很强的搜索问题,会遇到搜索中的多种优化方法,首先比较关键的是找到剪枝方法,本题最终通过适当维护变量进行可行性剪枝和最优性剪枝,非常 work;其次为了尽早剪枝,搜索顺序需要改变;然后在搜索过程中会遇到重复子问题,通过哈希表记录当前的参数此前是否搜索过。
前面的搜索优化到最后,会发现是一个记忆化搜索,因此本题也可以优化一下状态表示,然后用动态规划解决。
$1 题目
你正在安装一个广告牌,并希望它高度最大。这块广告牌将有两个钢制支架,两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子,如果钢筋的长度为 1、2 和 3,则可以将它们焊接在一起形成长度为 6 的支架。
返回广告牌的最大可能安装高度。如果没法安装广告牌,请返回 0。
提示:
1 | 0 <= rods.length <= 20 |
示例 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: 搜索
- 基本搜索:考虑前 根,有的放左,有的放右,有的不选,每一根有三种可能的处理方式。
- 搜索时维护左边高度 ,右边高度 。
剪枝
额外维护一个 remain,记录剩余的钢筋的长度之和。
可行性剪枝
如果剩余长度已经不够覆盖差值,那么即使全都取上也不能能形成合法的广告牌高度。则不用再继续搜索了。
1 | if(abs(lh - rh) > remain) |
最优性剪枝
剩余的长度即使全都用上,可能形成的最高高度,也不会比之前取得过的最高高度更高,则不用再继续搜索了。
1 | if(lh + rh + remain <= ans * 2) |
实践中这些剪枝非常 work。
搜索顺序
为了尽早剪枝,应该让较长的钢筋先搜索。
记忆化搜索
这样在搜索过程中,对于当前的状态 来说,可能会遇到很多重复情况,例如 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 | (1) |
当 继续变大的时候,重复子问题更多。因此需要考虑记忆化搜索,备忘录为 dp[i][lh][rh]
,是一个布尔值,表示 (i, lh, rh)
之前是否已经搜索过了。
这样如果搜索到状态 i, lh, rh
时,如果没被剪枝掉,则再查一下备忘录,如果之前没搜过,才继续搜索下去,否则之前已经搜索过并且在答案中更新了,直接返回。
等效性剪枝
lh
和 rh
如果互换,则对搜索结果无影响,也应该视为重复子问题,因此以下 lh=201, rh=202
与前面的两种情况是重复的。
1 | (3) |
也就是说如果之前搜索过 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 | class Solution { |
算法2: 动态规划
用左高和右高维护状态信息,改为用高度差和公共高度维护状态信息。
注意状态转移方程考虑“当前的状态会影响哪些状态”,而不是更常见的“哪些状态会影响当前状态”。
1 | 状态定义: |
代码 (C++)
1 | class Solution { |