leetcode.956. 最高的广告牌
你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
返回广告牌的最大可能安装高度。如果没法安装广告牌，请返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/tallest-billboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
DFS
剪枝：
- 1.abs(leftheight - rightheight) > remain[index] 加上剩余的支架也无法左右等高了
- 2.(leftheight + rightheight + remain[index]) <= ans + ans 加上剩余的支架也不会高于当前的答案
动态规划+DFS
动态规划
dp[k][i] 代表以第k个元素为尾,高度差为i,两支架的高度和
转移方程:
dp[k][i] = max(dp[k-1][i], dp[k-1][i+rods[k]]+rods[k],dp[k-1][abs(i-rods[k])]+rods[k])
tallestBillboard_5.cpp
动态规划
对于每一根钢筋 x，我们会写下 +x，-x 或者 0。我们的目标是最终得到结果 0 并让正数之和最大。我们记所有写下的正数之和为 score。例如，+1 +2 +3 -6 的 score 为 6。
dp[i][s] 表示以第i个元素为尾，数字和为s,可以得到的正的最大score
转移方程:
dp[i][s]=max(dp[i-1][s],dp[i-1][s-rods[i]]+rods[i],dp[i-1][s+rods[i]])
tallestBillboard_6.cpp