Math Dynamic Programming
Guru Level

Implement the minimumCostCutStick method that returns the minimum total cost to cut a stick at given positions.

You are given the length of a stick and an array of cut positions. When a stick segment is cut, the cost of that cut is the current segment length.

Return the minimum total cost required to perform all cuts. You may choose the order of cuts.

Example 1
Input:
length (int) = 7
cuts (int[]) = [1,3,4,5]
size (int) = 4
Return:
(int) 16
Example 2
Input:
length (int) = 9
cuts (int[]) = [5,6,1,4,2]
size (int) = 5
Return:
(int) 22
Example 3
Input:
length (int) = 5
cuts (int[]) = [2,4]
size (int) = 2
Return:
(int) 8

This is an interval dynamic programming problem.

Add positions 0 and length to the cuts list, then sort it. For each interval between two cut positions, try every internal cut as the first cut made inside that interval. The cost is the interval length plus the best cost of cutting the left and right parts.

Build answers from smaller intervals to larger intervals.

Pseudocode:

function minimumCostCutStick(length, cuts, size):
    positions = [0] + cuts + [length]
    sort positions
    m = positions.length
    dp = m by m table filled with 0
    for gap from 2 to m - 1:
        for left from 0 to m - gap - 1:
            right = left + gap
            dp[left][right] = infinity
            for cut from left + 1 to right - 1:
                cost = positions[right] - positions[left]
                cost += dp[left][cut] + dp[cut][right]
                dp[left][right] = min(dp[left][right], cost)
    return dp[0][m - 1]
Run your code to see the result.