553. The Cheapest Way to Cut a Stick
A stick runs from 0 to L. A list of positions must all be cut, in any order. Cutting a
piece costs the LENGTH of that piece, whatever position within it is chosen.
Print the smallest total cost.
L = 7, cuts at 1 3 4 5 -> 16
L = 5, cuts at 2 -> 5 one cut, one piece of length 5
## Why the order matters at all
Each cut splits one piece into two, and the cost is the length of the piece being cut. So cutting near the middle early leaves two short pieces and makes later cuts cheap, while cutting near an end leaves one long piece that stays expensive.
With a single cut position the cost is fixed at L regardless, which is why L = 5 with
one cut answers 5 and is worth stating: the ORDER only matters once there are at least two
cuts.
## The state
Sort the cut positions and pad with 0 and L:
pts = [0] + sorted(cuts) + [L]
dp[i][j] = the cheapest way to make every cut strictly between pts[i] and pts[j]
Padding turns "the piece currently spanning from here to there" into a pair of indices, and
the piece's length is just pts[j] - pts[i].
## The recurrence
dp[i][j] = (pts[j] - pts[i]) + min over k in (i, j) of dp[i][k] + dp[k][j]
The length term is paid ONCE per range, no matter which k is chosen first, because
whichever cut comes first in this piece costs the whole piece's length. Only what happens
after depends on k.
Pulling that constant out of the minimum is what makes the recurrence clean, and putting it inside would be equivalent but obscures why the choice is only about the two halves.
## Why the endpoints must be padded
Without the 0 and L sentinels the length of the current piece is not recoverable from
the state, and the first and last pieces need special handling.
With them, dp[i][i+1] is an empty range with no cuts to make, costing 0, and the loop
starts at length 2.
## Sorting is not optional
The cuts arrive in arbitrary order and the recurrence assumes pts is increasing, since it
uses pts[j] - pts[i] as a length. Forgetting to sort gives negative lengths and an answer
that is too small.
L = 9 with cuts 5 6 1 4 2 answers 22 and is the test: the input is deliberately
unsorted.
## Boundaries
L = 4 with cuts 1 3 answers 7: cut at 1 for 4 then at 3 for 3, or cut at 3 for 4 then at
1 for 3. Both give 7, so this input confirms the symmetry rather than distinguishing orders.
L = 12 with cuts 3 6 9 answers 24, where cutting the middle first is strictly better.
## Cost
Time O(m^3) where m is the number of cuts plus two. Space O(m^2).
Constraints - `2 ≤ L ≤ 1000000` - `1 ≤ m ≤ 100` - `0 < each cut position < L` - the positions are distinct
Input
The first line contains two integers L and m.
The second line contains m cut positions, in any order.
Output
Print the smallest total cost of making all the cuts.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.