Tallest Billboard
Problem
You are installing a billboard supported by two steel rods of equal height. You have a collection of rods (lengths in rods) and may weld several together to form a support. Each rod is used in the left support, the right support, or not at all. Return the largest possible height of the billboard (the common height of the two supports), or 0 if you cannot make two equal supports.
rods = [1, 2, 3, 6]6def tallest_billboard(rods):
# dp[diff] = max height of taller support for that difference
dp = {0: 0}
for r in rods:
cur = dict(dp)
for diff, taller in cur.items():
shorter = taller - diff
# add r to taller support
d = diff + r
dp[d] = max(dp.get(d, 0), taller + r)
# add r to shorter support
d = abs(shorter + r - taller)
dp[d] = max(dp.get(d, 0), max(taller, shorter + r))
return dp[0]function tallestBillboard(rods) {
let dp = { 0: 0 };
for (const r of rods) {
const cur = Object.assign({}, dp);
for (const key in cur) {
const diff = Number(key), taller = cur[key];
const shorter = taller - diff;
let d = diff + r;
dp[d] = Math.max(dp[d] || 0, taller + r);
d = Math.abs(shorter + r - taller);
dp[d] = Math.max(dp[d] || 0, Math.max(taller, shorter + r));
}
}
return dp[0];
}class Solution {
public int tallestBillboard(int[] rods) {
Map<Integer, Integer> dp = new HashMap<>();
dp.put(0, 0);
for (int r : rods) {
Map<Integer, Integer> cur = new HashMap<>(dp);
for (Map.Entry<Integer, Integer> e : cur.entrySet()) {
int diff = e.getKey(), taller = e.getValue();
int shorter = taller - diff;
int d = diff + r;
dp.put(d, Math.max(dp.getOrDefault(d, 0), taller + r));
d = Math.abs(shorter + r - taller);
dp.put(d, Math.max(dp.getOrDefault(d, 0), Math.max(taller, shorter + r)));
}
}
return dp.get(0);
}
}int tallestBillboard(vector<int>& rods) {
unordered_map<int, int> dp;
dp[0] = 0;
for (int r : rods) {
unordered_map<int, int> cur = dp;
for (auto& e : cur) {
int diff = e.first, taller = e.second;
int shorter = taller - diff;
int d = diff + r;
dp[d] = max(dp.count(d) ? dp[d] : 0, taller + r);
d = abs(shorter + r - taller);
dp[d] = max(dp.count(d) ? dp[d] : 0, max(taller, shorter + r));
}
}
return dp[0];
}Explanation
We want two stacks of rods of equal height. The clever trick is to not track both heights, but only the difference between the taller and the shorter stack. We keep a map dp where dp[diff] stores the best (largest) height of the taller stack for that difference.
Why the difference? Because what we ultimately need is dp[0] — the case where the two stacks are tied. By remembering, for each possible gap, the tallest we can make the taller side, we always keep the most promising state and throw away worse ones with the same gap.
For each rod r and each existing state, we try three choices: add r to the taller side (the gap grows), add it to the shorter side (the gap shrinks or flips), or skip it. We use abs(...) when adding to the shorter side because the shorter side might overtake the taller one.
Example: rods = [1, 2, 3, 6]. We can put {1, 2, 3} on one side (height 6) and {6} on the other (height 6). The difference becomes 0 with both at height 6, so dp[0] = 6.
At the end we simply return dp[0], the tallest equal-height pair of supports we managed to build.