Kimi LeetCode 3651. 带传送的最小路径成本 Rust实现

这是 LeetCode 3651「带传送的最小路径成本」的 Rust 实现。解题思路核心思想是分层动态规划按使用传送次数 0, 1, ..., k 逐层计算最小成本。1. 状态定义f[t][i][j] 表示使用恰好 t 次传送到达格子 (i, j) 的最小成本2. 普通移动只能向右或向下花费为目标格子的值3. 传送优化将格子按值分组按值从大到小处理。对于值相同的格子组维护一个全局最小值 mn表示使用 t-1 次传送到达这些格子的最小成本然后该组所有格子都可以通过传送以成本 mn 到达4. 逐层迭代每多一次传送机会先通过传送更新状态再通过普通移动向右/向下传播优化Rust 代码rustuse std::collections::HashMap;impl Solution {pub fn min_cost(grid: VecVeci32, k: i32) - i32 {let m grid.len();let n grid[0].len();let k k as usize;let inf: i32 i32::MAX / 2;// f[t][i][j]: 使用 t 次传送到达 (i, j) 的最小成本let mut f vec![vec![vec![inf; n]; m]; k 1];// 初始化0 次传送起点成本为 0f[0][0][0] 0;for i in 0..m {for j in 0..n {if i 0 {f[0][i][j] f[0][i][j].min(f[0][i - 1][j] grid[i][j]);}if j 0 {f[0][i][j] f[0][i][j].min(f[0][i][j - 1] grid[i][j]);}}}// 按值分组g[value] 所有值为 value 的格子坐标列表let mut g: HashMapi32, Vec(usize, usize) HashMap::new();for i in 0..m {for j in 0..n {g.entry(grid[i][j]).or_default().push((i, j));}}// 按值从大到小排序用于传送处理// 因为传送要求目标值 源值所以从大值往小值处理可以维护后缀最小值let mut keys: Veci32 g.keys().cloned().collect();keys.sort_by(|a, b| b.cmp(a));// 逐层处理传送次数 1..kfor t in 1..k {let mut mn inf;// 按值从大到小遍历mn 维护所有值 当前 key 的格子中// 使用 t-1 次传送的最小成本for key in keys {let pos g[key];// 更新 mn当前值 key 的所有格子使用 t-1 次传送的最小成本for (i, j) in pos {mn mn.min(f[t - 1][i][j]);}// 这些格子可以通过一次传送以成本 mn 到达for (i, j) in pos {f[t][i][j] mn;}}// 普通移动向右或向下更新 f[t]for i in 0..m {for j in 0..n {if i 0 {f[t][i][j] f[t][i][j].min(f[t][i - 1][j] grid[i][j]);}if j 0 {f[t][i][j] f[t][i][j].min(f[t][i][j - 1] grid[i][j]);}}}}// 答案使用 0..k 次传送到达终点的最小成本let mut ans inf;for t in 0..k {ans ans.min(f[t][m - 1][n - 1]);}ans}}关键点说明要点 说明按值分组 HashMapi32, Vec(usize, usize) 将相同值的格子归类避免每次传送都遍历整个网格从大到小排序 keys.sort_by(\|a, b\| b.cmp(a)) 确保处理值 v 时mn 已经包含了所有值 v 的格子的最小成本满足传送条件 grid[x][y] grid[i][j]分层 DP f 是三维数组 f[k1][m][n]分别对应传送次数、行、列INF 选择 i32::MAX / 2 防止加法溢出复杂度分析- 时间复杂度O((k log(mn)) × mn)其中 k 是最大传送次数m、n 是网格行列数。每组处理 O(mn)普通移动 O(mn)共 k 轮- 空间复杂度O(k × m × n)三维 DP 数组参考来源