Minimum cost to cut a stick

Array Dynamic Programming Sorting

62.8% acceptance

Feb 25, 2026

4811

159

Given a wooden stick of length n units. Given an integer array cuts where cuts[i] denotes a position you should perform a cut at. You should perform the cuts in order, you can change the order of the cuts as you wish. The cost of one cut is the length of the stick to be cut. Return the minimum total cost of the cuts.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(n: i32, mut cuts: Vec<i32>) -> i32 {
    cuts.push(0);
    cuts.push(n);
    cuts.sort();
    let m = cuts.len();
    // dp[i][j] = min cost to cut the segment [cuts[i], cuts[j]]
    let mut dp = vec![vec![0i32; m]; m];
    // Fill by increasing gap length
    for gap in 2..m {
      for i in 0..m - gap {
        let j = i + gap;
        dp[i][j] = i32::MAX;
        for k in i+1..j {
          let cost = dp[i][k] + dp[k][j] + cuts[j] - cuts[i];
          dp[i][j] = dp[i][j].min(cost);
        }
      }
    }
    dp[0][m - 1]
  }
}