leetcode 956

问题

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:

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

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

1
2
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.

分析

$dp[i][j] == h$ 表示使用 $rods[0..i]$ 中的一些珠子来构建两个柱子，高度差为 $j$ 时，最大可能的公共高度为 $h$ 。则当遍历到 $rods[i]$ 时，可以有三种选择，第一种选择是不使用 $rods[i]$，第二种选择是将 $rods[i]$ 加到高一点的柱子上，第三种选择是将 $rods[i]$ 加到低一点的柱子上。将 $rods[i]$ 加到哪个柱子上就取决于 $dp[i-1][k]$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        int n = rods.size();
        int s = accumulate(rods.begin(), rods.end(), 0);
        vector<vector<int>> dp(n+1, vector<int>(s+1, -1));
        // dp[0][rods[0]] = 0;
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            int h = rods[i-1];
            for (int j = 0; j <= s-h; ++j) {
                if (dp[i-1][j] == -1) continue;
                
                dp[i][j] = max(dp[i-1][j], dp[i][j]);
                
                dp[i][j+h] = max(dp[i][j+h], dp[i-1][j]);
                
                dp[i][abs(j-h)] = max(dp[i][abs(j-h)], dp[i-1][j]+min(j, h));
            }
        }
        
        return dp[n][0];
    }
};