Hard

题目描述

你正在安装一个广告牌，希望它有最大的高度。广告牌将有两个钢支柱，一个在每一边。每个钢支柱必须是相等的高度。

给你一组可以焊接在一起的钢筋。例如，如果你有长度为 1、2 和 3 的钢筋，你可以将它们焊接在一起制作一个长度为 6 的支柱。

返回广告牌安装的最大可能高度。如果无法支撑广告牌，返回 0。

示例 1：

输入：rods = [1,2,3,6]
输出：6
解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们的和相等 = 6。

示例 2：

输入：rods = [1,2,3,4,5,6]
输出：10
解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们的和相等 = 10。

示例 3：

输入：rods = [1,2]
输出：0
解释：广告牌无法支撑，所以我们返回 0。

提示：

  • 1 <= rods.length <= 20
  • 1 <= rods[i] <= 1000
  • sum(rods[i]) <= 5000

解题思路

这是一个典型的动态规划问题。题目要求将钢筋分成三组：左支柱、右支柱和不使用的钢筋，使得左右支柱高度相等且最大。

核心思路：

  1. 对于每根钢筋，我们有三种选择：放在左支柱、放在右支柱或者不使用
  2. 我们需要维护所有可能的"左支柱高度 - 右支柱高度"的差值状态
  3. 使用哈希表记录每个差值对应的左支柱的最大高度

状态转移：

  • dp[diff] 表示当左右支柱高度差为 diff 时，左支柱的最大高度
  • 对于每根钢筋 rod：
    • 放在左支柱：new_dp[diff + rod] = max(new_dp[diff + rod], dp[diff] + rod)
    • 放在右支柱：new_dp[diff - rod] = max(new_dp[diff - rod], dp[diff])
    • 不使用：保持原状态

优化细节：

  • 初始状态：dp[0] = 0（差值为0时，左支柱高度为0）
  • 最终答案：dp[0]（差值为0表示左右支柱高度相等）
  • 由于差值可能为负数，我们使用偏移量或者允许负键的数据结构

时间复杂度 O(n × sum)，其中 n 是钢筋数量，sum 是所有钢筋长度之和。空间复杂度 O(sum)。

代码实现

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        unordered_map<int, int> dp;
        dp[0] = 0;
        
        for (int rod : rods) {
            unordered_map<int, int> new_dp = dp;
            for (auto& [diff, height] : dp) {
                // 放在左支柱
                new_dp[diff + rod] = max(new_dp[diff + rod], height + rod);
                // 放在右支柱
                new_dp[diff - rod] = max(new_dp[diff - rod], height);
            }
            dp = new_dp;
        }
        
        return dp[0];
    }
};

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0: 0}  # diff -> max left height
        
        for rod in rods:
            new_dp = dp.copy()
            for diff, height in dp.items():
                # 放在左支柱
                new_diff = diff + rod
                new_dp[new_diff] = max(new_dp.get(new_diff, 0), height + rod)
                # 放在右支柱
                new_diff = diff - rod
                new_dp[new_diff] = max(new_dp.get(new_diff, 0), height)
            dp = new_dp
        
        return dp[0]

public class Solution {
    public int TallestBillboard(int[] rods) {
        var dp = new Dictionary<int, int>();
        dp[0] = 0;
        
        foreach (int rod in rods) {
            var newDp = new Dictionary<int, int>(dp);
            foreach (var kvp in dp) {
                int diff = kvp.Key;
                int height = kvp.Value;
                
                // 放在左支柱
                int newDiff = diff + rod;
                if (!newDp.ContainsKey(newDiff)) newDp[newDiff] = 0;
                newDp[newDiff] = Math.Max(newDp[newDiff], height + rod);
                
                // 放在右支柱
                newDiff = diff - rod;
                if (!newDp.ContainsKey(newDiff)) newDp[newDiff] = 0;
                newDp[newDiff] = Math.Max(newDp[newDiff], height);
            }
            dp = newDp;
        }
        
        return dp.GetValueOrDefault(0, 0);
    }
}

var tallestBillboard = function(rods) {
    let dp = new Map();
    dp.set(0, 0);
    
    for (let rod of rods) {
        let newDp = new Map(dp);
        for (let [diff, height] of dp) {
            // 放在左支柱
            let newDiff = diff + rod;
            newDp.set(newDiff, Math.max(newDp.get(newDiff) || 0, height + rod));
            
            // 放在右支柱
            newDiff = diff - rod;
            newDp.set(newDiff, Math.max(newDp.get(newDiff) || 0, height));
        }
        dp = newDp;
    }
    
    return dp.get(0) || 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × sum)n 为钢筋数量，sum 为所有钢筋长度之和，每根钢筋需要遍历所有已有状态
空间复杂度O(sum)哈希表存储所有可能的差值状态，最多有 O(sum) 个不同的差值

相关题目