LeetCode 956. 最高的广告牌

2020-08-08 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 956. 最高的广告牌

题意分析

给一堆钢筋 rods，要焊两根支架把广告牌撑起来。每根钢筋可以焊到左支架、焊到右支架，或者干脆不用（不能切割、不能重复使用）。广告牌成立的前提是两根支架高度完全相等，求能搭出的最大高度；搭不出来（只有高度 0 的平凡解）时返回 0。

题面里「高度相等」这四个字是整道题的题眼。它说明我们关心的从来不是两边各自有多高，而是两边差多少——只有差为 0 的方案才有效。这提示状态不该按「左边高度」来设计，而应该按「高度差」来设计。

再看约束：rods 长度不超过 20，每根长度不超过 1000，所有钢筋总长不超过 5000。这三个数字给出了非常明确的算法信号。长度 20 意味着朴素枚举是 $3^{20} \approx 3.5 \times 10^9$，刚好超出可接受范围，所以不能纯暴力；而总长 5000 意味着高度差的取值范围被限制在 [0, 5000]，状态数是可枚举的——这正是背包型 DP 的典型信号。题目把总长写进约束里，就是在明说「请用总和当维度」。

边界方面：允许一根都不用，所以答案至少是 0；rods 里所有元素都是正整数，不存在 0 长度钢筋；答案必然不超过总长的一半，因为两边高度相加不会超过总长。

解法：DP（按高度差 diff 转移）

核心思路

先看暴力。每根钢筋有「放左、放右、不用」三种选择，深搜到底后检查两边是否相等，取最大值。这是 $O(3^n)$，n = 20 时约 35 亿次，超时。

瓶颈在于搜索把「左边具体多高、右边具体多高」当成了两个独立维度记录，状态空间白白翻倍。观察：如果两个不同的方案走到了相同的高度差，那么它们对未来的影响完全一样——后面的钢筋怎么放、最终能不能配平，只取决于当前差值，与两边的绝对高度无关。既然如此，同一个差值下只需要保留「最有潜力」的那一个方案。

什么叫最有潜力？差值相同的两个方案，显然较矮那边越高越好，因为最终答案就等于配平后较矮那边的高度（配平时两边相等）。于是状态定义确定下来：

dp[diff] = 在已考虑的钢筋中，能使「左右高度差恰为 diff」的所有方案里，较矮那一侧的最大高度。

这里约定 diff >= 0，即总把较高的一侧记为「左」，这样 diff 与 -diff 就不必分开存。初始状态 dp[0] = 0，表示一根不用时两边都是 0、差为 0、较矮侧高度为 0。

每根钢筋 x 有三种转移，设当前状态为 (diff, best)：

不用：状态原样保留，dp'[diff] = max(dp'[diff], best)。

放到较高的一侧：差值扩大为 diff + x，较矮侧没变，所以 dp'[diff + x] = max(dp'[diff + x], best)。

放到较矮的一侧：较矮侧变成 best + x，新的差值是 |diff - x|。新的「较矮侧」高度需要分情况：若 x <= diff，加完仍是较矮侧，高度为 best + x；若 x > diff，它反超成了较高侧，此时较矮侧变成原来的较高侧，高度为 best + diff。两种情况可以合并写成 best + min(diff, x)——这一步的合并是本题代码最精巧的地方。

维持的不变量是：处理完前 k 根钢筋后，dp 中每个键值对 (diff, best) 都对应至少一个真实可行的放置方案，且 best 是该差值下较矮侧能达到的最大高度。转移的三条规则覆盖了第 k+1 根钢筋的全部选择，所以不变量可以逐根维持下去。

最终答案是 dp[0]——差为 0 意味着两边等高，而此时「较矮侧高度」就是广告牌高度。若 dp[0] 从未被更新过就是初始的 0，正好对应「搭不出来返回 0」。

为什么用哈希表而不是数组：差值理论上界是 5000，开数组也可行；但实际可达的差值往往稀疏得多（尤其钢筋长度都很大时），哈希表只存真正可达的状态，遍历时天然跳过空洞。

解题步骤

初始化 dp = {0: 0}：一根钢筋都没用时，差值为 0、较矮侧高度为 0。为什么只放这一个初始状态：其余差值此刻都不可达，若预先填入会引入不存在的方案。

逐根钢筋滚动：对每根 x，新建 next 并先整体复制一份 dp。这份复制就是「不用这根钢筋」的转移，一次拷贝顶掉一条规则，比在循环里逐条写更省事。

为什么必须用新表 next 而不是原地更新 dp：若在遍历 dp 的同时往 dp 里写，新产生的状态可能在本轮又被当成旧状态取用，等于同一根钢筋被使用了多次；这是 01 背包的经典陷阱，用滚动新表可以彻底避免，也不用去纠结遍历方向。

转移一：放到较高侧。d1 = diff + x，值仍是 best。为什么值不变：较矮侧一点没动，而 dp 记的正是较矮侧高度。

转移二：放到较矮侧。d2 = |diff - x|，值是 best + min(diff, x)。为什么取绝对值：状态约定 diff >= 0，钢筋加到矮侧后可能反超，反超后两侧身份互换，差值取绝对值即可复用同一个键空间。为什么值是 best + min(diff, x)：x 没反超时新矮侧就是它自己（best + x）；反超时新矮侧是原来的高侧（best + diff）；min 恰好一次写对两种情况。

取 max 合并：写入时都用 max(已有值, 新值)，保证同一差值只保留最优。默认值取 -1 而不是 0 也可以（高度非负，0 也安全），但用 -1 能明确区分「不可达」与「可达但高度为 0」。

返回 dp[0]：差为 0 的最大矮侧高度就是答案；键不存在时返回 0，对应无法配平。

以 rods = [1, 2, 3, 6] 走一遍（预期答案 6）。初始 dp = {0: 0}。
处理 1：从 (0, 0) 出发。放高侧得 (1, 0)；放矮侧得 d2 = |0 - 1| = 1、值 0 + min(0, 1) = 0，同样是 (1, 0)。合并后 dp = {0: 0, 1: 0}。（差为 0 时两边对称，两条转移重合，这是正常的。）
处理 2：从 (0, 0) 得 (2, 0)；从 (1, 0) 放高侧得 (3, 0)，放矮侧得 d2 = |1 - 2| = 1、值 0 + min(1, 2) = 1，即 (1, 1)——这一步就是「1 在矮侧、2 在高侧，矮侧高度 1，差值 1」。合并后 dp = {0:0, 1:1, 2:0, 3:0}。
处理 3：关键的几条——从 (3, 0) 放矮侧得 d2 = 0、值 0 + min(3, 3) = 3，即 (0, 3)，对应左边放 3、右边放 1+2，两边都是 3；从 (1, 1) 放矮侧得 d2 = 2、值 1 + min(1, 3) = 2，即 (2, 2)；从 (2, 0) 放矮侧得 d2 = 1、值 0 + min(2, 3) = 2，即 (1, 2)。此时 dp[0] = 3。
处理 6：从 (6, ...) 之类的新状态之外，真正有用的是从 (6, 0) 出发——先看 dp 中是否有 diff = 6 的状态。由前一轮可知存在 (6, 0)（0 + 6 得到，来自 (0, 0) 放高侧后再叠加，具体路径是 1+2+3 全放一侧的对称形式）。更直接的是：处理 6 时从 (0, 3) 放高侧得 (6, 3)；而从上一轮的 (6, 0)（即左边 6、右边 0）放矮侧得 d2 = 0、值 0 + min(6, 6) = 6，即 (0, 6)。于是 dp[0] = max(3, 6) = 6。
返回 6，对应方案：左支架用钢筋 6，右支架用 1 + 2 + 3，两边都是 6。

代码实现

class Solution {
    public int tallestBillboard(int[] rods) {
        // dp[diff] = 高度差为 diff 时，较矮一侧能达到的最大高度。
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);

        for (int x : rods) {
            // 复制一份即「这根不用」的转移，同时避免同一根被重复使用。
            Map<Integer, Integer> next = new HashMap<>(dp);
            for (Map.Entry<Integer, Integer> e : dp.entrySet()) {
                int diff = e.getKey();
                int best = e.getValue();

                // 放到较高的一侧：矮侧不变，差值变大。
                int d1 = diff + x;
                next.put(d1, Math.max(next.getOrDefault(d1, -1), best));

                // 放到较矮的一侧：可能反超，新矮侧高度为 best + min(diff, x)。
                int d2 = Math.abs(diff - x);
                int b2 = best + Math.min(diff, x);
                next.put(d2, Math.max(next.getOrDefault(d2, -1), b2));
            }
            dp = next;
        }
        return dp.getOrDefault(0, 0);
    }
}

func tallestBillboard(rods []int) int {
    // dp[diff] = 高度差为 diff 时，较矮一侧能达到的最大高度。
    dp := map[int]int{0: 0}

    for _, x := range rods {
        // 复制一份即「这根不用」的转移，同时避免同一根被重复使用。
        next := make(map[int]int, len(dp)*2+1)
        for k, v := range dp {
            next[k] = v
        }

        for diff, best := range dp {
            // 放到较高的一侧：矮侧不变，差值变大。
            d1 := diff + x
            if next[d1] < best {
                next[d1] = best
            }

            // 放到较矮的一侧：可能反超，新矮侧高度为 best + min(diff, x)。
            d2 := abs(diff - x)
            b2 := best + min(diff, x)
            if next[d2] < b2 {
                next[d2] = b2
            }
        }
        dp = next
    }
    return dp[0]
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(n \cdot S)$，其中 S 为所有钢筋长度之和（本题不超过 5000）。凭什么：外层遍历 n 根钢筋，内层遍历当前 dp 的全部状态；差值的取值范围是 [0, S]，所以状态数不超过 S + 1，每个状态做常数次哈希写入。实际可达状态往往远少于 S，哈希表只存可达键，跑得比上界快得多。

空间复杂度：$O(S)$。凭什么：任意时刻只同时存在 dp 与 next 两张表，每张最多 S + 1 个键；滚动更新后旧表即可回收，不需要按钢筋数保存 n 层状态。

关键点总结

当答案只关心「两组之差为零」时，就该把差值而不是绝对值设成状态维度，这一步能把二维状态压成一维，是分组配平类问题的通用降维手法。

状态值存什么要服务于答案：这里存「较矮侧高度」，因为配平时它就是答案；若存「较高侧高度」也能做，但转移式会更绕，答案提取也要多一步。

best + min(diff, x) 一行同时覆盖「没反超」与「反超」两种情形，是把绝对值状态用干净的关键；写不出这一行时可以先分支写，验证正确后再合并。

用「新表 + 整体复制」实现滚动，既表达了「不选」的转移，又天然杜绝同一物品被重复使用，比原地更新省去思考遍历方向的心智负担。

约束里的「总和不超过某个值」几乎总是在提示背包型 DP——把总和当维度，是从指数级搜索降到多项式的标准路径。

面试视角：先说 $3^n$ 暴力和它为什么超时，再说「相同差值的方案对未来等价」这个观察，最后写出状态定义。面试官最想听的就是状态定义那一句话，把 dp[diff] 的含义完整说清楚，代码几乎自动成立；若被追问空间优化，可以提「差值上界 5000，可以用长度 5001 的数组替代哈希表，配合 -1 表示不可达」。

易错点总结

错误写法：在遍历 dp 的同时直接往 dp 里写新状态 → 用例 rods = [1, 2] 中处理 1 时新产生的 (1, 0) 会在同一轮被再次取用，等于把同一根钢筋用了两次，得到不存在的方案。

错误写法：忘记复制一份作为「不用这根钢筋」的转移 → 用例 rods = [1, 2, 3, 6] 中每根都被强制使用，dp[0] 只能取到 3 而取不到 6，答案偏小。

错误写法：放到矮侧时值写成 best + x → 用例 rods = [1, 2] 中从 (0, 0) 加 1，得到 (1, 1) 而实际矮侧高度仍是 0，后续把这个虚高的值一路传下去，答案被放大。

错误写法：放到矮侧时值写成 best + diff → 用例 rods = [5, 6] 中从 (5, 0) 加 6，反超后新矮侧应是 5，写成 best + diff = 5 恰好蒙对；但从 (5, 0) 加 3 时正确值是 3，写成 5 就凭空多出高度。

错误写法：d2 忘记取绝对值 → 用例 rods = [1, 3] 中从 (1, 0) 加 3 得到键 -2，负键与正键分裂成两套状态，最终 dp[0] 拿不到本该配平的方案。

错误写法：写入时直接 put 覆盖而不取 max → 用例 rods = [3, 1, 2] 中差值 1 会先后被写入 0 与 1，后写的把更优值覆盖掉，答案偏小。

错误写法：getOrDefault 的默认值写成 Integer.MIN_VALUE 后又参与加法 → 用例中 best + min(diff, x) 在默认值上做加法会整型下溢变成大正数，dp[0] 返回一个巨大的错误答案。

错误写法：最后返回 dp 中的最大值而不是 dp[0] → 用例 rods = [1, 2] 中 dp 里存在 (3, 0)、(1, 1) 等状态，返回最大值会给出非配平方案的高度，答案错误。

错误写法：把状态定义成「左侧高度」并开二维数组 dp[i][left] → 用例中总长 5000 时状态数达 $20 \times 5000$ 尚可，但还需再记右侧高度才能判等，维度爆炸到 $5000^2$，内存不可接受。

错误写法：认为答案是总长的一半并直接做子集和判定 → 用例 rods = [1, 2, 3, 6] 总长 12，一半是 6 恰好正确；但用例 rods = [1, 2] 总长 3，一半不是整数，且正确答案是 0，这个思路对「允许不用」的情形完全失效。

错误写法：Go 里把 next 与 dp 指向同一个 map（只赋值不新建） → 用例 rods = [1, 2, 3] 中所有写入都落回原表，与原地更新同样导致重复使用钢筋。

相似题目

题目	难度	考察点
1049. 最后一块石头的重量 II	中等	同样求两组之差，但目标是差最小且每块必须使用，可直接转 01 背包
494. 目标和	中等	每个数只能取正负两种，没有「不用」这一选项，求方案数而非最值
416. 分割等和子集	中等	差为 0 的可行性判定，全部元素必须分完，答案是布尔值
474. 一和零	中等	二维容量的 01 背包，练的是多维度限制而不是差值压缩
805. 数组的均值分割	困难	需要同时约束元素个数与总和，用折半枚举而非单一差值状态
879. 盈利计划	困难	状态含「至少达到」的下界语义，转移时需要对边界做截断处理