Minimum Cost to Cut a Stick

Given unique internal cut positions cuts and a stick of length n, make every required cut exactly once. Each cut costs the length of the segment being cut at…

Given unique internal cut positions cuts and a stick of length n, make every required cut exactly once. Each cut costs the length of the segment being cut at that moment. You may choose the cut order. Return the minimum total cost, not the cut order. The interface takes cuts first and n second; the input array is not modified.

- 2 <= n <= 100000 - 1 <= cuts.length <= min(n - 1, 100) - Each cuts[i] is a distinct integer in 1..n - 1. - The visualizer supports at most 6 cuts; longer valid inputs remain coding inputs.

Example 1: input cuts = [1,3,4,5], n = 7; output 16. Cut at 3 first, paying 7; cut the left piece at 1, paying 3; cut at 5 then 4 on the right, paying 4 and 2. Total 16.

Example 2: input cuts = [6,1,3], n = 7; output 14. Cut at 3, then 1 and 6: the segment costs are 7, 3 and 4.

Example 3: input cuts = [1], n = 2; output 2. The only required cut costs the full length 2.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.