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

这是 LeetCode 3651「带传送的最小路径成本」的 Go 实现。解题思路核心思想是分层动态规划按使用传送次数 0, 1, ..., k 逐层计算最小成本。1. 状态定义f[t][i][j] 表示使用恰好 t 次传送到达格子 (i, j) 的最小成本2. 普通移动只能向右或向下花费为目标格子的值3. 传送优化将格子按值分组按值从大到小处理。对于值相同的格子组维护一个全局最小值 mn表示使用 t-1 次传送到达这些格子的最小成本然后该组所有格子都可以通过传送以成本 mn 到达4. 逐层迭代每多一次传送机会先通过传送更新状态再通过普通移动向右/向下传播优化Go 代码gopackage mainimport (mathsort)func minCost(grid [][]int, k int) int {m, n : len(grid), len(grid[0])inf : math.MaxInt32 / 2// f[t][i][j]: 使用 t 次传送到达 (i, j) 的最小成本f : make([][][]int, k1)for t : 0; t k; t {f[t] make([][]int, m)for i : 0; i m; i {f[t][i] make([]int, n)for j : 0; j n; j {f[t][i][j] inf}}}// 初始化0 次传送起点成本为 0f[0][0][0] 0for i : 0; i m; i {for j : 0; j n; j {if i 0 {f[0][i][j] min(f[0][i][j], f[0][i-1][j]grid[i][j])}if j 0 {f[0][i][j] min(f[0][i][j], f[0][i][j-1]grid[i][j])}}}// 按值分组g[value] 所有值为 value 的格子坐标列表g : make(map[int][][]int)for i : 0; i m; i {for j : 0; j n; j {x : grid[i][j]g[x] append(g[x], []int{i, j})}}// 按值从大到小排序用于传送处理keys : make([]int, 0, len(g))for key : range g {keys append(keys, key)}sort.Sort(sort.Reverse(sort.IntSlice(keys)))// 逐层处理传送次数 1..kfor t : 1; t k; t {mn : inf// 按值从大到小遍历mn 维护所有值 当前 key 的格子中// 使用 t-1 次传送的最小成本for _, key : range keys {pos : g[key]// 更新 mn当前值 key 的所有格子使用 t-1 次传送的最小成本for _, p : range pos {mn min(mn, f[t-1][p[0]][p[1]])}// 这些格子可以通过一次传送以成本 mn 到达for _, p : range pos {f[t][p[0]][p[1]] mn}}// 普通移动向右或向下更新 f[t]for i : 0; i m; i {for j : 0; j n; j {if i 0 {f[t][i][j] min(f[t][i][j], f[t][i-1][j]grid[i][j])}if j 0 {f[t][i][j] min(f[t][i][j], f[t][i][j-1]grid[i][j])}}}}// 答案使用 0..k 次传送到达终点的最小成本ans : inffor t : 0; t k; t {ans min(ans, f[t][m-1][n-1])}return ans}关键点说明要点 说明按值分组 map[int][][]int 将相同值的格子归类避免每次传送都遍历整个网格从大到小排序 sort.Sort(sort.Reverse(sort.IntSlice(keys))) 确保处理值 v 时mn 已经包含了所有值 v 的格子的最小成本满足传送条件 grid[x][y] grid[i][j]分层 DP f 是三维切片 f[k1][m][n]分别对应传送次数、行、列INF 选择 math.MaxInt32 / 2 防止加法溢出复杂度分析- 时间复杂度O((k log(mn)) × mn)其中 k 是最大传送次数m、n 是网格行列数。每组处理 O(mn)普通移动 O(mn)共 k 轮- 空间复杂度O(k × m × n)三维 DP 数组参考来源