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) =
7cuts (int[]) =
[1,3,4,5]size (int) =
4Returns (int)
16Example 2
Input
length (int) =
9cuts (int[]) =
[5,6,1,4,2]size (int) =
5Returns (int)
22Example 3
Input
length (int) =
5cuts (int[]) =
[2,4]size (int) =
2Returns (int)
8This 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run