Minimum Cost to Cut a Stick
Problem
A wooden stick of length n; cuts[] are the required cut positions. Cost of a cut equals the length of the piece you cut. Return the minimum total cost (cuts may be performed in any order).
n=7, cuts=[1,3,4,5]16def min_cost(n, cuts):
c = sorted([0] + cuts + [n])
m = len(c)
dp = [[0]*m for _ in range(m)]
for length in range(2, m):
for i in range(m - length):
j = i + length
dp[i][j] = min(dp[i][k] + dp[k][j] for k in range(i + 1, j)) + c[j] - c[i]
return dp[0][m-1]function minCost(n, cuts) {
const c = [0, ...cuts, n].sort((a, b) => a - b);
const m = c.length;
const dp = Array.from({length: m}, () => new Array(m).fill(0));
for (let len = 2; len < m; len++) {
for (let i = 0; i < m - len; i++) {
const j = i + len; let best = Infinity;
for (let k = i + 1; k < j; k++) best = Math.min(best, dp[i][k] + dp[k][j]);
dp[i][j] = best + c[j] - c[i];
}
}
return dp[0][m-1];
}class Solution {
public int minCost(int n, int[] cuts) {
int[] c = new int[cuts.length + 2];
c[0] = 0; c[c.length - 1] = n;
for (int i = 0; i < cuts.length; i++) c[i + 1] = cuts[i];
Arrays.sort(c);
int m = c.length;
int[][] dp = new int[m][m];
for (int len = 2; len < m; len++) for (int i = 0; i < m - len; i++) {
int j = i + len, best = Integer.MAX_VALUE;
for (int k = i + 1; k < j; k++) best = Math.min(best, dp[i][k] + dp[k][j]);
dp[i][j] = best + c[j] - c[i];
}
return dp[0][m-1];
}
}int minCost(int n, vector& cuts) {
vector c = cuts; c.push_back(0); c.push_back(n);
sort(c.begin(), c.end());
int m = c.size();
vector> dp(m, vector(m, 0));
for (int len = 2; len < m; len++) for (int i = 0; i < m - len; i++) {
int j = i + len, best = INT_MAX;
for (int k = i + 1; k < j; k++) best = min(best, dp[i][k] + dp[k][j]);
dp[i][j] = best + c[j] - c[i];
}
return dp[0][m-1];
} Explanation
The cost of a cut equals the length of the piece you cut it from, and you may perform the cuts in any order. This is classic interval DP: we think about each segment of the stick between two fixed cut positions and find the cheapest way to make all the cuts inside it.
First we add sentinels 0 and n to the cut list and sort it, giving boundary points c. Then dp[i][j] is the minimum cost to make every required cut strictly between positions c[i] and c[j].
For a segment, we try each interior cut k as the first cut to perform. That cut costs the full segment length c[j] - c[i], and then the segment splits into two independent subproblems dp[i][k] and dp[k][j]. We take the k that minimizes the total, and we process segments from shortest to longest so the smaller pieces are already solved.
Example: n=7, cuts=[1,3,4,5] become sentinels [0,1,3,4,5,7]. Choosing a good order of cuts brings the summed piece-lengths down to 16, reported at dp[0][m-1].
There are O(M²) segments and each tries up to M split points, so the total time is O(M³).