这是 LeetCode 3538. 合并得到最小旅行时间 的 Rust 实现。
思路
本题是划分型动态规划。恰好执行 `k` 次合并，等价于将原路标序列切分为 `n-k` 个连续段，每段的单位时间为该段内所有 `time` 之和。
状态定义： `dp[i][used][last]` 表示：
- 当前位于第 `i` 个路标
- 已经用了 `used` 次合并
- 当前连续段的单位时间从原数组下标 `last` 开始累加
转移： 从 `i` 跳到 `j`（`j > i`），消耗 `j-i-1` 次合并，当前段距离为 `position[j]-position[i]`，单位时间为 `sum(time[last..i])`。
复杂度： `O(n² × k²)`，由于 `n ≤ 50, k ≤ 10`，完全在时限内。
---
```rust
impl Solution {
pub fn min_travel_time(l: i32, n: i32, k: i32, position: Vec<i32>, time: Vec<i32>) -> i32 {
let n = n as usize;
let k = k as usize;
let position: Vec<i32> = position;
let time: Vec<i32> = 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];
// 枚举下一个路标 j
let 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];
// 下一段从 i+1 开始重新累加单位时间
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]
}
}
```
---
验证：
- 示例 1：`l=10, n=4, k=1, position=[0,3,8,10], time=[5,8,3,6]` → 62 ✓
- 示例 2：`l=5, n=5, k=1, position=[0,1,2,3,5], time=[8,3,9,3,3]` → 34 ✓
