Minimum Cost to Cut a Stick
Hard · Dynamic Programming · about 30 minutes
Asked at Microsoft, Amazon, Google, Bloomberg, Meta.
A stick of length n must be cut at the positions in cuts (any order you choose). Each cut costs the current length of the piece being cut. Return the minimum total cost.