Kimi LeetCode 3538. 合并得到最小旅行时间 Rust实现

这是 LeetCode 3538. 合并得到最小旅行时间 的 Rust 实现。思路本题是划分型动态规划。恰好执行 k 次合并等价于将原路标序列切分为 n-k 个连续段每段的单位时间为该段内所有 time 之和。状态定义 dp[i][used][last] 表示- 当前位于第 i 个路标- 已经用了 used 次合并- 当前连续段的单位时间从原数组下标 last 开始累加转移 从 i 跳到 jj i消耗 j-i-1 次合并当前段距离为 position[j]-position[i]单位时间为 sum(time[last..i])。复杂度 O(n² × k²)由于 n ≤ 50, k ≤ 10完全在时限内。---rustimpl Solution {pub fn min_travel_time(l: i32, n: i32, k: i32, position: Veci32, time: Veci32) - i32 {let n n as usize;let k k as usize;let position: Veci32 position;let time: Veci32 time;// 前缀和prefix[i] time[0] ... time[i-1]let mut prefix vec![0; n 1];for i in 0..n {prefix[i 1] prefix[i] time[i];}const INF: i32 i32::MAX / 2;// dp[i][used][last]let mut dp vec![vec![vec![INF; n]; k 1]; n];// 终点position[n-1]无需再行驶for used in 0..k {for last in 0..n {dp[n - 1][used][last] if used k { 0 } else { INF };}}// 从右往左填表for i in (0..n - 1).rev() {for used in 0..k {for last in 0..i {// 当前连续段的单位时间 sum(time[last..i])let rate prefix[i 1] - prefix[last];// 枚举下一个路标 jlet max_j (i 1 (k - used)).min(n - 1);for j in i 1..max_j {let merges j - i - 1;if used merges k {continue;}let distance position[j] - position[i];// 下一段从 i1 开始重新累加单位时间let next dp[j][used merges][i 1];if next INF {dp[i][used][last] dp[i][used][last].min(distance * rate next);}}}}}dp[0][0][0]}}---验证- 示例 1l10, n4, k1, position[0,3,8,10], time[5,8,3,6] → 62 ✓- 示例 2l5, n5, k1, position[0,1,2,3,5], time[8,3,9,3,3] → 34 ✓