🔗 🔴 956. Tallest Billboard

Problem Statement

題目簡述

給定一個整數陣列 rods，代表不同長度的鋼筋。你需要將它們焊接起來，搭建成兩個高度相等的廣告牌支架（每個支架由若干根鋼筋首尾相接組成，且兩組鋼筋不能重複使用同一根）。
求能搭建的最大廣告牌高度。如果無法搭建高度相同的兩個支架，則返回 00。

Constraints

約束條件

  • 1≤rods.length≤201 \le \text{rods.length} \le 20
  • 1≤rods[i]≤10001 \le \text{rods}[i] \le 1000
  • ∑rods[i]≤5000\sum \text{rods}[i] \le 5000

思路：動態規劃與折半搜索

本題的目標是從給定的鋼筋中選出兩個互不重疊的子集，使得它們的元素和相等，並最大化這個和。這相當於對於每根鋼筋，我們有三種決策：分配給第一座支架、分配給第二座支架、或者不分配。

方法一：動態規劃（0/1 背包的變形）

1. 樸素想法與瓶頸

最直觀的想法是使用二維動態規劃，定義狀態 f[i][j]f[i][j] 表示第一座支架高度為 ii、第二座支架高度為 jj 是否可行。
然而，鋼筋的總長度限制 ∑rods[i]≤5000\sum \text{rods}[i] \le 5000，這意味著狀態空間大小為 5000×5000=2.5×1075000 \times 5000 = 2.5 \times 10^7。在時間與空間複雜度上，這個二維狀態都是無法承受的。

2. 關鍵觀察：狀態壓縮

注意到我們最終只關心「兩座支架高度相等」的情況，即高度差為 00。在動態規劃推導的過程中，我們其實不需要分別記錄兩座支架的確切高度，只需要維護兩座支架的高度差。

關鍵觀察：帶符號的高度差

設第一座支架的高度為 h1h_1，第二座支架的高度為 h2h_2。定義兩者的差值（高度差）為 d=h1−h2d = h_1 - h_2。
我們可以用一個狀態 f[d]f[d] 來記錄：當高度差為 dd 時，第一座支架 h1h_1 的最大可能高度。

如此一來，原本需要兩個維度 (h1,h2)(h_1, h_2) 的狀態，就被成功壓縮成了一個維度（高度差 dd）。
當我們處理完所有鋼筋後，最終答案即為 f[0]f[0]（高度差為 00 時，第一座支架的最大高度）。

3. 轉化為 0/1 背包模型

在進行狀態壓縮後，本題便能優雅地抽象為一個體積可正可負的 0/1 背包問題：

  • 背包容量：高度差 dd。
  • 物品價值：第一座支架的高度 h1h_1。
  • 決策與轉移：每根鋼筋最多只能使用一次。對於長度為 xx 的鋼筋，抉擇如下：
    • 放第一座：高度差增加 xx（消耗容量 +x+x），第一座高度增加 xx（獲得價值 xx）。
    • 放第二座：高度差減少 xx（消耗容量 −x-x），第一座高度不變（獲得價值 00）。
    • 不分配：高度差不變（消耗容量 00），獲得價值 00。

最終目標即為：求背包容量恰好為 00 時的最大價值。

狀態轉移（刷表法）

本題的狀態轉移非常適合用刷表法（Push DP） 來思考：若當前已知高度差為 dd 時，第一座支架的最大高度為 f[d]f[d]。當前輪引入一根長度為 xx 的鋼筋時，我們可以用當前狀態去更新下一輪的新狀態 nfnf：

  1. 分配給第一座支架（高度差增大 xx，第一座高度增加 xx）：

    f[d]→+xnf[d+x]=max⁡(nf[d+x],f[d]+x)f[d] \xrightarrow{+x} nf[d + x] = \max(nf[d + x], f[d] + x)

  2. 分配給第二座支架（高度差減少 xx，第一座高度不變）：

    f[d]→−xnf[d−x]=max⁡(nf[d−x],f[d])f[d] \xrightarrow{-x} nf[d - x] = \max(nf[d - x], f[d])

  3. 不分配（狀態保持不變，程式中直接透過 nf = f.copy() 實現）：

    f[d]→nf[d]=max⁡(nf[d],f[d])f[d] \to nf[d] = \max(nf[d], f[d])

套路：哈希表簡化邊界

藉由允許高度差 dd 為負數，我們可以使用雜湊表（Python 中的 defaultdict）統一處理，免去因高度差正負造成的分類討論，使轉移公式極其對稱。

易錯點：初始化

初始時僅 f[0] = 0 合法，其餘高度差狀態在未被轉移前均不可達。

複雜度分析

  • 時間複雜度：O(N⋅S)\mathcal{O}(N \cdot S)，其中 NN 是鋼筋的數量（最大為 2020），SS 是所有鋼筋長度總和 ∑rods[i]\sum \text{rods}[i]（最大為 50005000）。
  • 空間複雜度：O(S)\mathcal{O}(S)。我們只需要存儲上一輪的哈希表狀態。

方法二：折半搜索（Meet in the Middle）

雖然方法一的動態規劃在總長度限制為 50005000 時非常高效，但如果題目中鋼筋的數值範圍變大（例如 rods[i]≤109\text{rods}[i] \le 10^9），但鋼筋的個數 NN 仍然很小（N≤20N \le 20），此時方法一會因為狀態差值範圍過大而失效。

因為 N≤20N \le 20，我們可以聯想到折半搜索。

技巧：折半搜索優化狀態空間

將鋼筋分成左右兩半，每半最多有 1010 根鋼筋。

  1. 對左半部分的鋼筋，使用方法一的動態規劃求出所有可能的高度差 dLd_L 下，第一座支架的最大高度，記為哈希表 LL。
  2. 對右半部分的鋼筋，同理求出所有可能的高度差 dRd_R 下，第一座支架的最大高度，記為哈希表 RR。

當我們要把這兩部分拼起來時，為了讓最終的總高度差為 00，必須滿足：

dL+dR=0  ⟹  dL=−dRd_L + d_R = 0 \implies d_L = -d_R

也就是說，如果我們在左半部分選擇了高度差為 dd 的方案，那麼在右半部分就必須選擇高度差為 −d-d 的方案。此時第一座支架的總高度為 L[d]+R[−d]L[d] + R[-d]。
我們遍歷左半部分哈希表的所有高度差 dd，若 −d-d 存在於右半部分哈希表中，則用 L[d]+R[−d]L[d] + R[-d] 更新答案的最大值。

複雜度分析

  • 時間複雜度：O(3N/2)\mathcal{O}(3^{N/2})。左右兩半部分分別有 N/2N/2 個元素，每一根鋼筋有 33 種選擇（放左邊、放右邊、不放），因此最壞情況下的狀態數為 O(3N/2)\mathcal{O}(3^{N/2})。在 N=20N=20 時，310=590493^{10} = 59049。
  • 空間複雜度：O(3N/2)\mathcal{O}(3^{N/2})，用於存儲左右兩半部分的哈希表狀態。

類題

Code

方法一：動態規劃（維護高度差）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # 令 h1 表示支架 1 的高度，h2 表示支架 2 的高度， d = h1 - h2
        # f[d] 表示當 h1 - h2 = d 時，h1 的最大值
        f = defaultdict(int)
        f[0] = 0
        for x in rods:
            nf = f.copy()
            for d, h in f.items():
                nf[d + x] = max(nf[d + x], h + x)  # 分配給 h1
                nf[d - x] = max(nf[d - x], h)  # 分配給 h2
                # nf[d] = max(nf[d], h)  # 不分配，但已經包含在 f.copy() 內了
            f = nf
        return f[0]

方法二：折半搜索（Meet in the Middle）

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
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        n = len(rods)
        mid = (n + 1) // 2

        def build(rods: list[int]) -> defaultdict:
            # 定義同 Solution1
            f = defaultdict(int)
            f[0] = 0
            for x in rods:
                nf = f.copy()
                for d, h in f.items():
                    nf[d + x] = max(nf[d + x], h + x)
                    nf[d - x] = max(nf[d - x], h)
                f = nf
            return f

        # Meet in the middle
        L = build(rods[:mid])
        R = build(rods[mid:])
        ans = 0
        # 當 h1_l - h2_l = d 時，需要找到 h1_r - h2_r = -d 的情況，
        # 才能讓 h1_l + h1_r = h2_l + h2_r，此時可以得到的最大 h1 = L[d] + R[-d]
        for d, h in L.items():
            if -d in R:
                ans = max(ans, h + R[-d])
        return ans