最高的广告牌

此题解使用了分治加动态规划的方法。首先将钢筋数组分为两部分，对每部分独立求解可能的差值和相应的最大高度。这里使用一个字典来存储从差值到最大高度的映射。对于每根钢筋，更新两种情况：将它加到一边或从一边减去。这样，可以得到包含所有可能差值的字典。然后，将两部分的结果合并，查找两个字典中相反的键（即差值相等但符号相反，表示两边可以平衡），并计算这些情况的最大高度。最终结果是所有匹配差值组合中的最大高度。

时间复杂度: O(2^(n/2))

空间复杂度: O(2^(n/2))

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        def h(rods):
            f = defaultdict(int)  # 创建一个默认值为int的字典
            f[0] = 0  # 初始化差值为0的情况，最大高度也是0
            for x in rods:  # 遍历每根钢筋
                for diff, height in list(f.items()):  # 临时列表避免在迭代中修改字典
                    f[diff+x] = max(f[diff+x], height+x)  # 将钢筋加到一边的情况
                    f[diff-x] = max(f[diff-x], height)  # 将钢筋减去的情况
            return f 
        n = len(rods)
        l = h(rods[:n//2])  # 处理前半部分
        r = h(rods[n//2:])  # 处理后半部分
        ans = 0
        for i in l:  # 遍历第一部分的结果
            if -i in r:  # 查找相反差值的存在
                ans = max(ans, l[i]+r[-i])  # 如果存在，更新最大高度
        return ans