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:

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

这道题说是要装个很高的广告牌，有很多长度不同的支撑杆，多个支撑杆可以粘合成一个更长的，广告牌需要两个长度相等的支撑杆，问广告牌最高能放多高。去掉这个具体的场景，其实这道题讨论的就是在数组中选取若干个数字分成和相同的两组，问这个最大和是多少。跟之前那道 Partition Equal Subset Sum 非常的类似，不过那道题是要用到所有的数字，所以一旦可以分割的话，那么最大和就是固定的，为数组所有数字之和的一半。而这道题不强制要用所有的数字，所以最大和是不确定的。所以之前那道题的方法在这里完全不适用，但也不是完全没有关系，起码动态规划 Dynamic Programming 的思想还是要用的。博主强调过很多次，像这种数组啊，字符串啊之类的极值问题，DP 解法十有八九绕不开，若还是个 Hard 题，那么基本就是 DP 无疑了。这道题的一大难点就是 dp 不容易定义，即便你知道要用 DP，是否能写出正确的定义式也是个问题。下面这种解法参考了 zxybazh 大神的帖子，这里我们定一个一个二维 dp 数组，其中 dp[i][j] 表示从前i个数字中选出数字组成两组（组0和组1，这里假设组0数字之和一定小于组1），此时的二者中的较大长度，其实也就是组1的数字之和，并且j表示二组数字之和的差值。接下来就是要找出状态转移方程，如何从之前的状态推导出 dp[i][j]。当把 rod[i] 加入其中的一组时，此时有三种情况：

• 将 rod[i] 加入组1时，由于组1的数字和大，所以增加新数字会拉大两组原本的差值，若加入之后的差值为j，则加入之前则为 j-rods[i]，所以可以用 dp[i-1][j-rods[i]] + rods[i] 来更新 dp[i][j]。

• 将将 rod[i] 加入组0时，且加入之后组0的数字之和仍小于组1，但此时二者的差距变小了，若加入之后的差值为j，则加入之前则为 j+rods[i]，所以可以用 dp[i-1][j+rods[i]] 来更新 dp[i][j]。

• 将将 rod[i] 加入组0时，且加入之后组0的数字之和超过了组1，说明这个新数字要大于原本两个组之间的差值，若加入之后的差值为j，则加入之前则为 rods[i]-j，所以可以用 dp[i-1][rods[i]-j] + j 来更新 dp[i][j]。

搞清楚了这三种情况，就可以写出代码了，最终的结果是存在 dp[n][0] 中的，因为这表示从前n个数字中选出数字组成两组，且两组之和差为0，说明可以组成相同和的两组，参见代码如下：

解法一：

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
    	int n = rods.size();
        vector<vector<int>> dp(n + 1, vector<int>(5001));
        for (int i = 0; i <= 5000; i++) dp[0][i] = -1e9;
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
        	for (int j = 0; j <= 5000; ++j) {
        		dp[i][j] = dp[i - 1][j];
        		if (j >= rods[i - 1]) {
        			dp[i][j] = max(dp[i][j], dp[i - 1][j - rods[i - 1]] + rods[i - 1]);
        		} else {
        			dp[i][j] = max(dp[i][j], dp[i - 1][rods[i - 1] - j] + j);
        		}
        		if (j + rods[i - 1] <= 5000) {
        			dp[i][j] = max(dp[i][j], dp[i - 1][j + rods[i - 1]]);
        		}
        	}
        }
        return dp[n][0];
    }
};

再来看一种空间复杂度更小的解法，这里就照着 lee215 大神的帖子 来讲解吧。定义了一个一维数组 dp，其中 dp[i] 表示两组中较小的那组的数字之和，且i表示两组的数字和的差值。其中 dp[0] 要初始化为0。现在假设有两组数字，其和的差值为d，如下所示：

------- y ------|----- d -----|

------- y ------|

现在要加入一个新的数字x的话，还是有三种情况：

• 加入到长的那组，使得长的更长，此时要用 y 来更新 dp[d+x]，如下所示：

------- y ------|----- d -----|----- x -----|

------- y ------|

• 加入到短的那组，加了之后还是没有超过长的组，此时要用 y+x 来更新 dp[d-x]，如下所示：

-------y------|----- d -----|

-------y------|--- x ---|

• 加入到短的那组，加了之后超过了长的组，此时要用 y+d 来更新 dp[x-d]，如下所示：

------- y ------|----- d -----|

------- y ------|------- x -------|

可以发现，后两种情况可以合成为一种，dp[abs(x - d)] = max(dp[abs(x - d)], y + min(d, x))，最终的结果保存在 dp[0] 中，参见代码如下：

解法二：

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
    	vector<int> dp(5001, -1e9);
    	dp[0] = 0;
    	for (int x : rods) {
    		vector<int> cur = dp;
    		for (int d = 0; d + x <= 5000; ++d) {
    			dp[d + x] = max(dp[d + x], cur[d]);
    			dp[abs(d - x)] = max(dp[abs(d - x)], cur[d] + min(d, x));
    		}
    	}
    	return dp[0];
    }
};

Github 同步地址:

#956

类似题目：

Partition Equal Subset Sum

参考资料：

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

https://leetcode.com/problems/tallest-billboard/discuss/203274/Simple-C%2B%2B-DP-beating-100-O(NM)

https://leetcode.com/problems/tallest-billboard/discuss/203181/JavaC%2B%2BPython-DP-min(O(SN2)-O(3N2-*-N)

LeetCode All in One 题目讲解汇总(持续更新中...)