网硕互联帮助中心2026-01-19：带传送的最小路径成本。用go语言，给定一个 m×n 的整数矩阵 grid 和一个整数 k。起点是左上角格子 (0,0)，终点是右下角格子 (m−1,n−1)。你可以用两种方式前进：
-
相邻移动：向右或向下走一步（从 (i,j) 到 (i,j+1) 或 (i+1,j)），代价等于你进入的那个格子的数值；
-
传送：从当前格子跳到任意一个数值不大于当前格子的格子（grid[x][y] ≤ grid[i][j]），传送不消耗代价，但最多只能使用 k 次。
目标是计算从起点到终点所需的最小总费用（所有移动代价之和）。
2 <= m, n <= 80。
m == grid.length。
n == grid[i].length。
0 <= grid[i][j] <= 10000。
0 <= k <= 10。
输入: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2。
输出: 7。
解释:
| (0, 0) | 向下移动 | (1, 0) | 0 + 2 = 2 |
| (1, 0) | 向右移动 | (1, 1) | 2 + 5 = 7 |
| (1, 1) | 传送到 (2, 2) | (2, 2) | 7 + 0 = 7 |
我们最初在 (0, 0)，成本为 0。
题目来自力扣3651。
🧠 算法过程详解
初始化与边界检查
算法首先获取网格的行数 m 和列数 n。它进行了一项关键检查：如果允许传送（k > 0）并且起点的值大于终点的值（grid[0][0] > grid[m-1][n-1]），则可以直接从起点传送到终点，总成本为0，算法直接返回0。这是因为传送规则允许跳到任意数值不大于当前格子的格子，且不消耗代价。
确定数值范围并初始化关键数组
算法遍历整个网格，找到其中最大的数值 mx，这定义了问题中格子数值的范围。
接着，初始化三个关键数组：
- sufMinF: 大小为 mx+2。sufMinF[x] 用于记录在当前迭代中，到达某个格子后，能够通过一次传送到达所有数值小于等于 x 的格子所需的最小累计成本。初始时，其每个元素被设置为一个极大值（math.MaxInt）。
- minF: 大小为 mx+1。在当前行的计算过程中，minF[x] 临时记录到达当前行某个数值为 x 的格子的最小累计成本。每次计算新的一行前会被重置为极大值。
- f: 大小为 n+1。这是一个动态规划数组，用于进行空间优化的路径计算。f[j] 代表在当前行，到达第 j 列格子的最小累计成本（注意索引偏移，f[1] 对应第0列）。
核心迭代：模拟最多 k 次传送机会
算法进行 k+1 次迭代（因为最多可以使用 k 次传送，包括0次）。每次迭代包含两个主要阶段：动态规划计算当前路径成本和更新传送优化信息。
-
阶段一：动态规划计算路径成本
在此阶段，算法忽略传送，计算从起点到每个格子的最小路径成本，规则是只能向右或向下移动，进入一个格子的成本是该格子的值。它使用滚动数组 f 进行空间优化：- 初始化 f 为极大值，并设置 f[1] = -grid[0][0]。这是因为起点（左上角）的成本不计入（根据题目描述，代价等于“进入的那个格子的数值”，起点是出发点，不应算作“进入”）。
- 遍历每一行 i：
- 遍历该行的每一列 j 和对应的格子值 x：
- 计算 f[j+1] 的新值。它考虑两种移动方式：
- 从左边格子向右移动过来：成本是 f[j] + x。
- 从上边格子向下移动过来：成本是 f[j+1] + x（这里的 f[j+1] 是上一行同一列的值，在遍历过程中被保留）。
- 关键点：此外，它还考虑第三种可能，即通过一次传送到达当前格子。这个信息来自 sufMinF[x]，它代表了在之前的状态下，通过一次传送到达数值为 x 的格子的最小成本。
- f[j+1] 取这三种情况的最小值。
- 遍历该行的每一列 j 和对应的格子值 x：
- 在计算完一行的 f 值后，更新 minF 数组：对于当前行的每个数值 x，minF[x] 更新为所有数值为 x 的格子的 f 值中的最小值。
阶段二：更新传送优化信息
这个阶段基于本轮动态规划计算出的 minF 来更新 sufMinF，为下一次迭代（即多使用一次传送）做准备。
- sufMinF[i] 被更新为 min(sufMinF[i+1], minF[i])。这个操作是从大到小遍历数值，计算 sufMinF 的后缀最小值。其物理意义是：sufMinF[x] 现在表示，在本轮迭代后，可以通过一次传送到达数值 小于等于 x 的任意格子的最小成本。
- 算法检查 sufMinF 数组是否在本轮迭代中发生了变化。如果没有变化（done 为 true），说明传送操作已经无法提供更优的路径，提前终止迭代。
返回结果
在完成所有迭代后，数组 f 的最后一个元素 f[n] 就包含了到达终点（右下角）的最小总成本，将其返回。
⏱️ 复杂度分析
-
时间复杂度：该算法的时间复杂度为 O(k * m * n * mx)。
- 最外层循环是 k 次迭代。
- 每次迭代中，需要遍历整个 m x n 的网格，复杂度为 O(m * n)。
- 在每次迭代的最后，需要遍历 minF 数组（大小为 mx）来更新 sufMinF，复杂度为 O(mx)。
- 因此，总复杂度是三者相乘。其中 mx 是网格中数值的最大值，在本题约束下（grid[i][j] <= 10000），mx 是一个常数上限（10000），但仍然是复杂度分析中的一个因子。
-
空间复杂度：该算法的空间复杂度为 O(n + mx)。
- 主要空间消耗在于 sufMinF 数组（O(mx)）、minF 数组（O(mx)）和动态规划数组 f（O(n)）。
- 算法使用了滚动数组技术，避免存储整个 m x n 的DP表，从而将空间复杂度降低到与网格维度无关的水平。
💎 总结
这个算法的核心思想是通过多次迭代（模拟使用传送次数）来逐步优化路径成本。在每次迭代中，它先计算不使用额外传送时的基础路径成本，然后利用上一轮迭代得到的传送信息（sufMinF）来更新当前路径成本的可能性。通过维护基于格子数值的代价后缀最小值数组，高效地捕捉了传送操作带来的优化效果。
Go完整代码如下：
package main
import (
"fmt"
"math"
"slices"
)
func minCost(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
if k > 0 && grid[0][0] > grid[m–1][n–1] {
return 0
}
mx := 0
for _, row := range grid {
mx = max(mx, slices.Max(row))
}
sufMinF := make([]int, mx+2)
for i := range sufMinF {
sufMinF[i] = math.MaxInt
}
minF := make([]int, mx+1)
f := make([]int, n+1)
for range k + 1 {
for i := range minF {
minF[i] = math.MaxInt
}
// 64. 最小路径和（空间优化写法）
for i := range f {
f[i] = math.MaxInt / 2
}
f[1] = –grid[0][0] // 起点的成本不算
for _, row := range grid {
for j, x := range row {
f[j+1] = min(f[j]+x, f[j+1]+x, sufMinF[x])
minF[x] = min(minF[x], f[j+1])
}
}
done := true
// 计算 minF 的后缀最小值
for i := mx; i >= 0; i— {
mn := min(sufMinF[i+1], minF[i])
if mn < sufMinF[i] {
sufMinF[i] = mn
done = false
}
}
if done {
// 收敛了：传送不改变 sufMinF，那么无论再传送多少次都不会改变 sufMinF
break
}
}
return f[n]
}
func main() {
grid := [][]int{{1, 3, 3}, {2, 5, 4}, {4, 3, 5}}
k := 2
result := minCost(grid, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
import math
from typing import List
def minCost(grid: List[List[int]], k: int) –> int:
m, n = len(grid), len(grid[0])
if k > 0 and grid[0][0] > grid[m–1][n–1]:
return 0
mx = max(max(row) for row in grid)
sufMinF = [math.inf] * (mx + 2)
minF = [math.inf] * (mx + 1)
f = [math.inf] * (n + 1)
for _ in range(k + 1):
for i in range(len(minF)):
minF[i] = math.inf
# 64. 最小路径和（空间优化写法）
for i in range(len(f)):
f[i] = math.inf / 2
f[1] = –grid[0][0] # 起点的成本不算
for row in grid:
for j, x in enumerate(row):
f[j+1] = min(f[j] + x, f[j+1] + x, sufMinF[x])
if f[j+1] < minF[x]:
minF[x] = f[j+1]
done = True
# 计算 minF 的后缀最小值
for i in range(mx, –1, –1):
mn = min(sufMinF[i+1], minF[i])
if mn < sufMinF[i]:
sufMinF[i] = mn
done = False
if done:
# 收敛了：传送不改变 sufMinF，那么无论再传送多少次都不会改变 sufMinF
break
return int(f[n])
if __name__ == "__main__":
grid = [[1, 3, 3], [2, 5, 4], [4, 3, 5]]
k = 2
result = minCost(grid, k)
print(result)
C++完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int minCost(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
if (k > 0 && grid[0][0] > grid[m–1][n–1]) {
return 0;
}
// 找到矩阵中的最大值
int mx = 0;
for (const auto& row : grid) {
for (int val : row) {
mx = max(mx, val);
}
}
vector<int> sufMinF(mx + 2, INT_MAX);
vector<int> minF(mx + 1, INT_MAX);
vector<int> f(n + 1, INT_MAX / 2);
for (int _ = 0; _ <= k; ++_) {
// 重置 minF
fill(minF.begin(), minF.end(), INT_MAX);
// 64. 最小路径和（空间优化写法）
fill(f.begin(), f.end(), INT_MAX / 2);
f[1] = –grid[0][0]; // 起点的成本不算
for (const auto& row : grid) {
for (int j = 0; j < n; ++j) {
int x = row[j];
// 计算三个可能值的最小值
int val1 = f[j] + x;
int val2 = f[j + 1] + x;
int val3 = sufMinF[x];
f[j + 1] = min({val1, val2, val3});
if (f[j + 1] < minF[x]) {
minF[x] = f[j + 1];
}
}
}
bool done = true;
// 计算 minF 的后缀最小值
for (int i = mx; i >= 0; —i) {
int mn = min(sufMinF[i + 1], minF[i]);
if (mn < sufMinF[i]) {
sufMinF[i] = mn;
done = false;
}
}
if (done) {
// 收敛了：传送不改变 sufMinF，那么无论再传送多少次都不会改变 sufMinF
break;
}
}
return f[n];
}
int main() {
vector<vector<int>> grid = {{1, 3, 3}, {2, 5, 4}, {4, 3, 5}};
int k = 2;
int result = minCost(grid, k);
cout << result << endl;
return 0;
}
评论前必须登录！
注册