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

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

Related Topics:
Dynamic Programming

## Solution 1. DP

### Thought

For each rod x, we have 3 options:

1. use it in one post
2. use it in another post
3. 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);
}