leetcode 956. 最高的广告牌「动态规划」

题目思路

给定若干钢筋，需要把它们分成两组，使两组高度相同，并让这个相同高度尽可能大。

直接枚举两组集合会爆炸。一个更自然的状态是记录两边高度差 diff，以及在这个差值下较矮一边能达到的最大高度。

状态定义

令 dp[diff] 表示当前处理过的钢筋中，两组高度差为 diff 时，较矮一边的最大高度。

处理一根长度为 x 的钢筋时有三种选择：

• 不使用。
• 放到较高一侧，差值变成 diff + x。
• 放到较低一侧，差值变成 abs(diff - x)，较矮边高度会增加 min(diff, x)。

目标是 dp[0]。

代码

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        unordered_map<int, int> dp;
        dp[0] = 0;

        for (int x : rods) {
            auto old = dp;
            for (auto [diff, low] : old) {
                dp[diff + x] = max(dp[diff + x], low);

                int nextDiff = abs(diff - x);
                int nextLow = low + min(diff, x);
                dp[nextDiff] = max(dp[nextDiff], nextLow);
            }
        }

        return dp[0];
    }
};

复杂度

如果钢筋总和为 $S$，状态数量最多为 $S$，时间复杂度约为 $O(nS)$。

这个题的关键不是公式，而是找到“差值 + 较矮边最大高度”这个状态表达。