0956._Tallest_Billboard.md

956. Tallest Billboard

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/tallest-billboard/

内容描述

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 1:

Input: [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
Example 2:

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.
Example 3:

Input: [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.
 

Note:

0 <= rods.length <= 20
1 <= rods[i] <= 1000
The sum of rods is at most 5000.

解题方案

思路 1 - 时间复杂度: O(2^N)- 空间复杂度: O(N)******

开始想的递归，加了一些剪枝，naive，超时

class Solution:
    def tallestBillboard(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """
        rods = sorted(rods)[::-1]
        self.res = 0
        sums = sum(rods)
        
        def chose(rods, idx, sum1, sum2):
            if idx == len(rods):
                return
            if sum1 > sums / 2 or sum2 > sums / 2:
                return
            if sum1 == sum2:
                self.res = max(self.res, sum1)
            chose(rods, idx+1, sum1, sum2)
            
            if sum1 + rods[idx]== sum2:
                self.res = max(self.res, sum2)
            chose(rods, idx+1, sum1+rods[idx], sum2)
            
            if sum1 == sum2+ rods[idx]:
                self.res = max(self.res, sum1)
            chose(rods, idx+1, sum1, sum2+rods[idx])

        chose(rods, 0, 0, 0)
        return self.res

思路 2 - 时间复杂度: O(M * N)- 空间复杂度: O(N)******

Time Complexity:
O(NM), where we have
N = rod.length <= 20
S = sum(rods) <= 5000
M = all possible sum = min(3^N, S)

只有抄答案了，见https://leetcode.com/problems/tallest-billboard/discuss/203181/JavaC%2B%2BPython-DP-min(O(SN2)-O(3N2-*-N)了

又学到新知识了

dp[diff] = a 代表有这样一对 height:(a, a+diff)

class Solution:
    def tallestBillboard(self, rods):
        """
        :type rods: List[int]
        :rtype: int
        """
        dp = {0: 0}
        for rod in rods:
            cur = {key: dp[key] for key in dp}
            for diff in cur:
                dp[diff+rod] = max(dp.get(diff+rod, 0), cur[diff])
                dp[abs(diff-rod)] = max(dp.get(abs(diff-rod), 0), cur[diff] + min(diff, rod))
        return dp[0]