这道题的核心解法是斜率优化DP (Convex Hull Trick)。Rust 的实现思路与 Python / Java 一致，但需要利用其强大的泛型和迭代器来写出更安全、高效的代码。

📝 核心思路回顾

状态转移方程可变形为查询直线 y = m*x + c 在 x = pref[i] 处的最小值，其中直线参数为：

· 斜率 m = -2 * pref[j]
· 截距 c = dp_prev[j] + pref[j] * pref[j] - pref[j]

通过维护一个下凸包 (Lower Hull) 并用双端队列 (VecDeque) 来保证 O(1) 的查询和插入。

💻 Rust 代码实现

```rust
use std::collections::VecDeque;

impl Solution {
pub fn min_partition_score(nums: Vec<i32>, k: i32) -> i64 {
let n = nums.len();
let k = k as usize;

// 1. 计算前缀和 (使用 i64 防止溢出)
let mut pref = vec![0i64; n + 1];
for (i, &num) in nums.iter().enumerate() {
pref[i + 1] = pref[i] + num as i64;
}

// 2. 初始化 dp_prev: 只分 1 段的情况 (存储两倍分数)
let mut dp_prev = vec![0i64; n + 1];
for i in 1..=n {
let s = pref[i];
dp_prev[i] = s * (s + 1); // 两倍分数，避免浮点数
}

// 3. 迭代分段数从 2 到 k
for _ in 2..=k {
let mut dp_cur = vec![0i64; n + 1];
let mut hull: VecDeque<(i64, i64)> = VecDeque::new(); // (斜率 m, 截距 c)

for i in 1..=n {
let j = i - 1;
// 将新的候选直线 (基于 j) 加入凸包
if j >= 1 {
let m = -2 * pref[j];
let c = dp_prev[j] + pref[j] * pref[j] - pref[j];
Self::add_line(&mut hull, m, c);
}

// 查询在 x = pref[i] 处的最优值
if !hull.is_empty() {
while hull.len() >= 2 {
let (m1, c1) = hull[0];
let (m2, c2) = hull[1];
// 如果第一条直线在 x 处不比第二条优，则弹出
if m1 * pref[i] + c1 >= m2 * pref[i] + c2 {
hull.pop_front();
} else {
break;
}
}
let (best_m, best_c) = hull[0];
dp_cur[i] = best_m * pref[i] + best_c + pref[i] * pref[i] + pref[i];
} else {
// 处理不可能的状态（如 i < 当前分段数）
dp_cur[i] = i64::MAX / 4;
}
}
dp_prev = dp_cur;
}

// 最终答案除以 2 (因为全程使用两倍分数)
dp_prev[n] / 2
}

// 辅助函数：向凸包中添加直线 (维护下凸包)
fn add_line(hull: &mut VecDeque<(i64, i64)>, m: i64, c: i64) {
// 检查新直线是否会让队尾的直线变得无用
while hull.len() >= 2 {
let (m1, c1) = hull[hull.len() - 2];
let (m2, c2) = hull[hull.len() - 1];
// 判断 (c2 - c1) * (m1 - m) >= (c - c1) * (m1 - m2)
// 使用交叉相乘避免浮点数
if (c2 - c1) * (m1 - m) >= (c - c1) * (m1 - m2) {
hull.pop_back();
} else {
break;
}
}
hull.push_back((m, c));
}
}
```

⏳ 复杂度分析

· 时间复杂度: O(k * n)。每个状态至多入队出队一次。
· 空间复杂度: O(n)。用于存储 DP 数组和凸包。

这个 Rust 实现直接翻译了斜率优化的核心逻辑，并利用 i64 安全地处理了所有整数运算，避免了溢出风险。