Minimum Cost to Cut a Stick LeetCode solution in Rust

1
impl Solution {
2
  pub fn min_cost(n: i32, cuts: Vec<i32>) -> i32 {
3
    let mut a = Vec::with_capacity(cuts.len() + 2);
4
    a.push(0);
5
    a.push(n);
6
    a.extend(cuts);
7
    a.sort_unstable();
8

9
    let mut dp = vec![vec![0; a.len()]; a.len()];
10

11
    for len in 2..a.len() {
12
      for i in 0..a.len() - len {
13
        let j = i + len;
14

15
        let mut t = i32::MAX;
16
        for k in i + 1..j {
17
          t = t.min(dp[i][k] + dp[k][j]);
18
        }
19
        dp[i][j] = t + a[j] - a[i];
20
      }
21
    }
22

23
    dp[0][a.len() - 1]
24
  }
25
}