Formatted question description: https://leetcode.ca/all/956.html
956. Tallest Billboard (Hard)
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.
Related Topics:
Dynamic Programming
Solution 1. DP
Thought
For each rod x
, we have 3 options:
 use it in one post
 use it in another post
 don’t use it.
If we turn all the numbers used in the first post to negative (turn x
to x
), leave the numbers used in the second post asis (x
to +x
), and turn all the numbers that are not used to 0
, this question turns into:
Find the max score we can get after doing the above operations. The “score” is the sum of all the positive numbers. For example, +1 +2 +3 6
has a score of 6
.
Since sum(rods)
is bounded, it suggests us to use this fact in some way.
A fact we should consider is that for a given sum
, it doesn’t matter how we get the sum
.
For example, with rods = [1,2,2,3]
, we could get sum 3
in 3 different ways. If we just consider sum = 3
, we actually covered all those three cases.
Since sum
is in range [5000, 5000]
, we just have 10001
numbers to consider.
Algorithm
Let dp[i][s]
be the largest score we can get using rods[(i+1)..(N1)]
to get sum s
.
For example, for rods = [1,2,3,6]
, we have dp[1][1] = 5
, because after writing 1
, we could write +2 +3 6
to get sum 1
, and the corresponding score is 5
.
For the base case, dp[rods.length][s]
is 0
when s == 0
, and infinity
everywhere else.
The recursion is dp[i][s] = max(dp[i+1][s], dp[i+1][srods[i]], rods[i] + dp[i+1][s+rods[i]])
.
NOTE: in the following implementation we use sum = 5000
as sum = 0
to simply code.
// OJ: https://leetcode.com/problems/tallestbillboard
// Time: O(NS) where N is the length of `rods`,
// and S is the maximum of `sum(rods[i..j])`
// Space: O(NS)
// Ref: https://leetcode.com/articles/tallestbillboard/
class Solution {
private:
vector<vector<int>> dp;
int dfs(vector<int>& rods, int i, int s) {
if (i == rods.size()) return s == 5000 ? 0 : INT_MIN;
if (dp[i][s] != INT_MIN) return dp[i][s];
int ans = dfs(rods, i + 1, s);
ans = max(ans, dfs(rods, i + 1, s  rods[i]));
ans = max(ans, rods[i] + dfs(rods, i + 1, s + rods[i]));
return dp[i][s] = ans;
}
public:
int tallestBillboard(vector<int>& rods) {
int N = rods.size();
dp = vector<vector<int>>(N, vector<int>(10001, INT_MIN));
return dfs(rods, 0, 5000);
}
};
Java

class Solution { public int tallestBillboard(int[] rods) { int rows = rods.length; if (rows < 2) return 0; int sum = 0; for (int rod : rods) sum += rod; int columns = sum * 2 + 1; int[][] dp = new int[rows][columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) dp[i][j] = 1; } dp[0][sum + rods[0]] = rods[0]; dp[0][sum] = 0; dp[0][sum  rods[0]] = 0; for (int i = 1; i < rows; i++) { for (int j = 0; j < columns; j++) { if (dp[i  1][j] >= 0) { int rod = rods[i]; dp[i][j + rod] = Math.max(dp[i][j + rod], dp[i  1][j] + rod); dp[i][j] = Math.max(dp[i][j], dp[i  1][j]); dp[i][j  rod] = Math.max(dp[i][j  rod], dp[i  1][j]); } } } int maxHeight = 0; for (int i = 0; i < rows; i++) maxHeight = Math.max(maxHeight, dp[i][sum]); return maxHeight; } }

Todo

# 956. Tallest Billboard # https://leetcode.com/problems/tallestbillboard/ class Solution: def tallestBillboard(self, rods: List[int]) > int: dp = dict() dp[0] = 0 for x in rods: curr = defaultdict(int) for s in dp: curr[s + x] = max(curr[s + x], dp[s] + x) curr[s] = max(curr[s], dp[s]) curr[s  x] = max(curr[s  x], dp[s]) dp = curr return dp[0]