Tallest Billboard
Hard · Dynamic Programming · Array · Dynamic Programming
Problem
You are building a billboard that rests on two steel supports of equal height. You have a collection of rods; each support is made by welding together some of the rods. Each rod goes into at most one support, or is left unused.
Return the largest possible height of the billboard. If the two supports cannot be made equal with a positive height, return 0.
Examples
Input: rods = [2,4,5,7] Output: 9
Weld 2 + 7 for one support and 4 + 5 for the other: height 9.
Input: rods = [1,3] Output: 0
The two rods have different lengths, and one rod cannot make two supports.
Input: rods = [5,5,5,5] Output: 10
Two rods per support gives height 10.
Constraints
- 1 <= len(rods) <= 20
- 1 <= rods[i] <= 1000
- sum(rods) <= 5000
Approaches
- Try every assignment — time O(3^n), space O(n) recursion
Follow-up
Why index by the difference and not by both heights? The future only cares how far apart the supports are: the same remaining rods can close the same gap no matter how tall the supports already are. So for each gap only the tallest pair is worth keeping, and the table has at most sum + 1 entries. The second use case reads the same table at differences up to a tolerance.
Related problems
Start free on Cariara · Coding problems · System design studio
