The cheapest way to cut a stick

def min_cut_cost(n, cuts):
    p = [0] + sorted(cuts) + [n]           # boundaries
    m = len(p)
    cost = [[0] * m for _ in range(m)]     # cost[i][j]: every cut strictly between p[i] and p[j]
    for gap in range(2, m):
        for i in range(m - gap):
            j = i + gap
            cost[i][j] = p[j] - p[i] + min(cost[i][k] + cost[k][j] for k in range(i + 1, j))   # k cut first
    return cost[0][m - 1]

#include <algorithm>
#include <climits>
#include <vector>

long long solve(int n, std::vector<int> cuts) {
    std::sort(cuts.begin(), cuts.end());
    std::vector<long long> p{0};
    for (int c : cuts) p.push_back(c);
    p.push_back(n);
    const int m = p.size();
    std::vector<std::vector<long long>> cost(m, std::vector<long long>(m, 0));
    for (int gap = 2; gap < m; ++gap)
        for (int i = 0; i + gap < m; ++i) {
            int j = i + gap;
            long long best = LLONG_MAX;
            for (int k = i + 1; k < j; ++k) best = std::min(best, cost[i][k] + cost[k][j]);   // k cut first
            cost[i][j] = best + p[j] - p[i];
        }
    return cost[0][m - 1];
}

class Solution {
    public long minCutCost(int n, int[] cuts) {
        int[] sorted = cuts.clone();
        java.util.Arrays.sort(sorted);
        int m = sorted.length + 2;
        long[] p = new long[m];
        p[m - 1] = n;
        for (int i = 0; i < sorted.length; i++) p[i + 1] = sorted[i];
        long[][] cost = new long[m][m];
        for (int gap = 2; gap < m; gap++)
            for (int i = 0; i + gap < m; i++) {
                int j = i + gap;
                long best = Long.MAX_VALUE;
                for (int k = i + 1; k < j; k++) best = Math.min(best, cost[i][k] + cost[k][j]);   // k cut first
                cost[i][j] = best + p[j] - p[i];
            }
        return cost[0][m - 1];
    }
}

function minCutCost(n, cuts) {
  const p = [0, ...[...cuts].sort((a, b) => a - b), n], m = p.length;
  const cost = Array.from({ length: m }, () => new Array(m).fill(0));
  for (let gap = 2; gap < m; gap++)
    for (let i = 0; i + gap < m; i++) {
      const j = i + gap;
      let best = Infinity;
      for (let k = i + 1; k < j; k++) best = Math.min(best, cost[i][k] + cost[k][j]);   // k cut first
      cost[i][j] = best + p[j] - p[i];
    }
  return cost[0][m - 1];
}

fn solve(n: i64, cuts: &[i64]) -> i64 {
    let mut p = vec![0i64];
    let mut sorted = cuts.to_vec();
    sorted.sort();
    p.extend(sorted);
    p.push(n);
    let m = p.len();
    let mut cost = vec![vec![0i64; m]; m];
    for gap in 2..m {
        for i in 0..m - gap {
            let j = i + gap;
            let best = (i + 1..j).map(|k| cost[i][k] + cost[k][j]).min().unwrap();   // k cut first
            cost[i][j] = best + p[j] - p[i];
        }
    }
    cost[0][m - 1]
}

import Data.Array
import Data.List (sort)

solve :: Int -> [Int] -> Int
solve n cuts = cost ! (0, m - 1)
  where
    ps = [0] ++ sort cuts ++ [n]
    m = length ps
    p = listArray (0, m - 1) ps
    -- cost ! (i, j): making every cut strictly between boundaries i and j
    cost = array ((0, 0), (m - 1, m - 1)) [((i, j), go i j) | i <- [0 .. m - 1], j <- [0 .. m - 1]] :: Array (Int, Int) Int
    go i j
      | j - i < 2 = 0
      | otherwise = p ! j - p ! i + minimum [cost ! (i, k) + cost ! (k, j) | k <- [i + 1 .. j - 1]]