hardDynamic Programming 2DPure DSA~45 min
Minimum Cost To Split Log
A log segment of length n must be split at a set of marked offsets. Each split costs the current length of the piece being cut. Splits can be performed in any order; choose the order that minimizes total cost.
Problem
Given an integer n (the length of a stick from 0 to n) and an array cuts of positions to cut, return the minimum total cost. The cost of one cut is the length of the stick segment it is performed on; cuts may be done in any order.
Input
An integer n and an array cuts of m positions in (0, n), 1 ≤ m ≤ 100.
Output
An integer: the minimum total cutting cost.
Constraints
- 2 ≤ n ≤ 10^6
- 1 ≤ m ≤ min(n−1, 100)
- All cut positions are distinct and strictly inside (0, n)
Examples
Example 1
Input
n = 7, cuts = [1,3,4,5]
Output
16
An optimal order (e.g. cut at 3 first) yields total cost 16.
Example 2
Input
n = 9, cuts = [5,6,1,4,2]
Output
22
The best ordering of the five cuts costs 22.