Minimum Cost to Cut a Stick

You are given a stick of length n and an array cuts representing cut positions. Each cut costs the current length of the stick being cut. Return the minimum total cost to perform all cuts. Pattern focus: Interval DP. Choose the last cut inside an interval and combine the cost of left and right parts.

Input Format

n = stick length, cuts = cut positions

Output Format

minimum total cutting cost

Constraints

  • 2 <= n <= 10^6
  • 1 <= cuts.length <= 100
  • 1 <= cuts[i] < n
  • All cuts are distinct

Examples

Example 1:

Input:

n = 7
cuts = [1,3,4,5]

Output:

16

Explanation:

This is the standard example: the optimal order yields total cost 16.

Example 2:

Input:

n = 9
cuts = [5,6,1,4,2]

Output:

22

Explanation:

The minimum total cost for these cut positions is 22.

Example 3:

Input:

n = 8
cuts = [3,4,5]

Output:

17

Explanation:

An optimal order is to cut around the middle first.

Loading...
Minimum Cost to Cut a Stick - Dp Advanced