有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置，
你可以按顺序完成切割，也可以根据需要更改切割的顺序，
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。
对棍子进行切割将会把一根木棍分成两根较小的木棍，
这两根木棍的长度和就是切割前木棍的长度。
返回切棍子的最小总成本。
输入：n = 9, cuts = [5,6,1,4,2]。
输出：22。
步骤如下：
1.将切割点数组 cuts 排序，并构建新的数组 arr，将 0 和 n 加入其中，得到长度为 m+2 的数组。
2.初始化一个 m+2 行 m+2 列的 DP 数组 dp，dp[i][j] 表示将区间 [i,j] 内的木棍切割成最小块的总成本。初始化值为 -1。
3.定义递归函数 process(arr, l, r, dp)，表示计算将 arr[l…r+1] 这段木棍切割成若干小块的最小总成本。
4.在 process 函数中，分三种情况讨论：
当 l > r 时，说明该区间内没有木棍需要切割，返回 0。
当 l == r 时，说明该区间只有一根木棍，成本为该木棍的长度。
当 dp[l][r] != -1 时，说明该区间的最小成本已经被计算过，直接返回结果 dp[l][r]。5.在 process 函数中，枚举所有可能的切割点 k，计算将 arr[l…k] 和 arr[k+1…r+1] 两段木棍切割成最小块的总成本，并加上当前区间的长度（即 arr[r+1]-arr[l-1]），得到该切割点下的总成本。取最小值作为答案。
6.将答案缓存到 dp[l][r] 中，并返回结果。
7.在主函数中，调用 min_cost(n, &cuts) 函数，得到切割最小总成本。
该算法的时间复杂度为 O(n ^ 3)，空间复杂度为 O(n^2)。其中，nn 表示初始木棒的长度，即 n 变量的值。
时间复杂度分析：
在递归函数中，共有 n 个区间需要计算最小成本，对于每个区间，枚举所有可能的切割点需要 O(n) 的时间复杂度，因此总时间复杂度为 O(n^3)。
空间复杂度分析：
DP 数组的大小为 (n+1)×(n+1)，因此空间复杂度为 O(n^2)。同时，在递归过程中，由于使用了备忘录技巧，栈深度最大为 O(n)，因此空间复杂度也可以看作是 O(n) 级别的。
rust代码如下：
// 计算给定切割点下的最小成本
fn min_cost(n: i32, cuts: &[i32]) -> i32 {
let m = cuts.len();
// 将切割点排序并构建数组
let mut arr = vec![0; m + 2];
arr[0] = 0;
for i in 1..=m {
arr[i] = cuts[i - 1];
}
arr[m + 1] = n;
// 初始化 DP 数组
let mut dp = vec![vec![-1; m + 2]; m + 2];
process(&arr, 1, m, &mut dp)
}
// 递归函数，计算给定区间的最小成本
fn process(arr: &[i32], l: usize, r: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
// 如果区间为空，则成本为 0
if l > r {
return 0;
}
// 如果区间只有一个元素，则成本为该元素的长度
if l == r {
return arr[r + 1] - arr[l - 1];
}
// 如果 DP 数组中已经计算过当前区间的最小成本，则直接返回结果
if dp[l][r] != -1 {
return dp[l][r];
}
// 枚举所有可能的切割点，计算最小成本
let mut ans = i32::max_value();
for k in l..=r {
ans = min(ans, process(arr, l, k - 1, dp) + process(arr, k + 1, r, dp));
}
// 加上当前区间的长度，并将结果缓存到 DP 数组中
ans += arr[r + 1] - arr[l - 1];
dp[l][r] = ans;
// 返回最终结果
ans
}
fn main() {
let n = 7;
let cuts = [1, 3, 4, 5];
let cost = min_cost(n, &cuts);
println!("{}", cost); // 输出：16
}![2023-03-28：有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。 给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置， 你可以按顺序完成切割，也可](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2023/05/23/a8c040d8911747aaa064469b8083af3a.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2023-03-28：有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。 给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置， 你可以按顺序完成切割，也可")
