Welcome to Subscribe On Youtube
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 <= 201 <= rods[i] <= 1000The 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 as-is (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)..(N-1)] 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][s-rods[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/tallest-billboard
// 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/tallest-billboard/
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);
}
};
-
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; } } ############ class Solution { public int tallestBillboard(int[] rods) { int n = rods.length; int s = 0; for (int x : rods) { s += x; } int[][] f = new int[n + 1][s + 1]; for (var e : f) { Arrays.fill(e, -(1 << 30)); } f[0][0] = 0; for (int i = 1, t = 0; i <= n; ++i) { int x = rods[i - 1]; t += x; for (int j = 0; j <= t; ++j) { f[i][j] = f[i - 1][j]; if (j >= x) { f[i][j] = Math.max(f[i][j], f[i - 1][j - x]); } if (j + x <= t) { f[i][j] = Math.max(f[i][j], f[i - 1][j + x] + x); } if (j < x) { f[i][j] = Math.max(f[i][j], f[i - 1][x - j] + x - j); } } } return f[n][0]; } } -
# 956. Tallest Billboard # https://leetcode.com/problems/tallest-billboard/ 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] -
func tallestBillboard(rods []int) int { n := len(rods) s := 0 for _, x := range rods { s += x } f := make([][]int, n+1) for i := range f { f[i] = make([]int, s+1) for j := range f[i] { f[i][j] = -(1 << 30) } } f[0][0] = 0 for i, t := 1, 0; i <= n; i++ { x := rods[i-1] t += x for j := 0; j <= t; j++ { f[i][j] = f[i-1][j] if j >= x { f[i][j] = max(f[i][j], f[i-1][j-x]) } if j+x <= t { f[i][j] = max(f[i][j], f[i-1][j+x]+x) } if j < x { f[i][j] = max(f[i][j], f[i-1][x-j]+x-j) } } } return f[n][0] } func max(a, b int) int { if a > b { return a } return b } -
function tallestBillboard(rods: number[]): number { const s = rods.reduce((a, b) => a + b, 0); const n = rods.length; const f = new Array(n).fill(0).map(() => new Array(s + 1).fill(-1)); const dfs = (i: number, j: number): number => { if (i >= n) { return j === 0 ? 0 : -(1 << 30); } if (f[i][j] !== -1) { return f[i][j]; } let ans = Math.max(dfs(i + 1, j), dfs(i + 1, j + rods[i])); ans = Math.max( ans, dfs(i + 1, Math.abs(j - rods[i])) + Math.min(j, rods[i]), ); return (f[i][j] = ans); }; return dfs(0, 0); }