题目
You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.
You have a collection of rods which can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.
Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.
Example
Input: [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
Note
0 <= rods.length <= 20
1 <= rods[i] <= 1000
The sum of rods is at most 5000.
分析
- 这道题目用 递归 是可以做出来的，但是既然本题是放在 dp 类别里面。就应该尝试用 dp 来解决
尝试思路一： 使用状态压缩 dp （不行）
尝试思路二： 使用 二进制表示每个数字的归属（10101 表示第一、三、五的数字属于 组二， 第二、四数字属于组一。 不行，因为每个数字有 3 个状态，即属于组一、属于组二、不属于任何组）
尝试思路三：常规的数组的类的 dp 都是 dp[i+1] = func( dp[i]) (i 为数组序号)。 这次改成 dp[diff] = max(left, right) （为什么能想到这个，我也不知道。大概是头脑风暴吧）
class Solution(object):
def tallestBillboard(self, rods):
"""
:type rods: List[int]
:rtype: int
"""
total = sum(rods)
if 2 > len(rods):
return 0
dp, stack = [0]*(total/2+10), []
for v in rods:
for i in range(len(dp)):
if i > dp[i]:
continue
if total/2 + 1 > i+v:
stack.append((i+v, max(dp[i+v], dp[i]+v)))
if i - v >= 0 :
stack.append((i-v, max(dp[i-v], dp[i])))
else:
stack.append((v-i, max(dp[v-i], dp[i]-i+v)))
for vv in stack:
p, value = vv[0], vv[1]
if value > dp[p]:
dp[p] = value
stack = []
return dp[0]
Runtime: 548 ms, faster than 55.56% of Python online submissions for Tallest Billboard.
Memory Usage: 13 MB, less than 97.62% of Python online submissions for Tallest Billboard.、
结果不是很理想， 内存很省但是速度不是很快～～
看了网络上的一个比我速度快的解答，思路和我一样。但是他用了 字典，我用数组～。哎
这道题目，只要是 dp 的。大家的思路都一样。真是醉了