956. 最高的广告牌

Difficulty
Hard
Tags
动态规划
URL
https://leetcode-cn.com/problems/tallest-billboard/
Star
你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
返回广告牌的最大可能安装高度。如果没法安装广告牌，请返回 0。
示例 1：
输入：[1,2,3,6]
输出：6
解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。
示例 2：
输入：[1,2,3,4,5,6]
输出：10
解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。
示例 3：
输入：[1,2]
输出：0
解释：没法安装广告牌，所以返回 0。
提示：
  1. 0 <= rods.length <= 20
  1. 1 <= rods[i] <= 1000
  1. 钢筋的长度总和最多为 5000
通过次数4,249提交次数9,639

法1 动态规划 三维 dp

思路
对于每一根钢筋都有选择与不选择，所以为经典的背包问题
状态定义
dp[i][j][k] 仅仅使用前 i 个钢筋是否可以达到左边高度j，右边高度k
状态转移
  • 不选择当前钢筋 dp[i][j][k] = dp[i-1][j][k]
  • 选择当前钢筋：选择放在左边or 选择放在右边 dp[i][j][k] = dp[i-1][j-rods[i-1]][k] or dp[i][j][k-rods[i-1]]
题解
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        # dp[i][j] 仅仅使用前 i 个钢筋是否可以达到左边高度j，右边高度k
        target = sum(rods) // 2 + 1
        dp = [[[False]*(target+1) for _ in range(target+1)] for _ in range(len(rods)+1)]
        # 高度 0 肯定是可以的
        dp[0][0][0] = True
        res = 0
        for i in range(1, len(rods)+1):
            for j in range(0, target+1):
                for k in range(0, target+1):
                    # 默认不使用当前 钢筋
                    dp[i][j][k] = dp[i-1][j][k]
                    # 如果不使用当前钢筋达不到 左 j 右 k ,再取考虑使用当前钢筋
                    # 使用当前钢筋时需要考虑是在左边用还是在右边用
                    if dp[i][j][k] is False:
                        # 装在左边 是否可行
                        if j - rods[i-1] >= 0 and dp[i-1][j-rods[i-1]][k]:
                            dp[i][j][k] = True
                        # 装在右边 是否可行
                        if k - rods[i-1] >= 0 and dp[i-1][j][k-rods[i-1]]:
                            dp[i][j][k] = True
                    
                    # 更新结果
                    if dp[i][j][k] and j == k:
                        res = max(res, j)
   
        return res

动态规划 nb

思路
将问题转化为求数组和为0时的组合
对任何一个数，可以用三种方式对待它，乘以1，-1或0，目标是求和为0时的最大正数和 例如，[1，2，3], 可以对1，2乘以1，3乘以-1，此时和为0， 最大正数和为1+2=3 用字典来存储每一步的结果，键和值分别是(k:v) 总和以及正数和， 初始化时dp={0:0},表示和为0时的最大长度为0 那么最后只需要求dp[0]的最大值就好了   遍历所有钢筋： 对每根钢筋都有三种处理方式：加，减，丢 （对应乘以1，-1或0）   如：[1,2,3] 第一步: 用钢筋1，对初始的0，操作 如果加，那么总和是1，正数是1；如果减，总和是-1，正数0；如果丢，维持不变；更新dp={0:0, 1:1, -1:0} 第二步: 用钢筋2，对第一步中dp的键0，1，-1的基础上分别进行“加，减，丢 ”的操作 在0:0基础上，如果加，也就是变为2：2；如果减，变为 -2：0； 如果丢，变成0：0 类似的，在1：1基础上，加减丢变为3：3，-1：1，1：1 类似的，在-1：0基础上，加减丢变为1：2，-3：0，-1：0 每个键取较大值，用粗体标识了，然后更新dp={0:0, 1:2, 2:2, -1:1, 3:3, -2:0, -3:0} 总和为1时，相比第一步时的正数和为1，第二步时正数和变为了2，将dp[1]修改为更大的2 总和为-1时，相比第一步时的正数和为0，第二步时正数和变为了1，将dp[-1]修改为更大的1 最后返回dp[0]
题解
class Solution:
    def tallestBillboard(self, rods):
        dp = {0: 0}
        for i in rods:
            for k, b in list(dp.items()):
                dp[k + i] = max(dp.get(k + i, 0), b + i)
                dp[k - i] = max(dp.get(k - i, 0), b)
        
        return dp[0]
参考