这道题的核心解法是斜率优化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 代码实现rustuse std::collections::VecDeque;impl Solution {pub fn min_partition_score(nums: Veci32, 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 到 kfor _ 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 安全地处理了所有整数运算避免了溢出风险。
这道题的核心解法是斜率优化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 代码实现rustuse std::collections::VecDeque;impl Solution {pub fn min_partition_score(nums: Veci32, 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 到 kfor _ 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 安全地处理了所有整数运算避免了溢出风险。
