目标
给你一个 m x n 的二维整数数组 grid 和一个整数 k。你从左上角的单元格 (0, 0) 出发，目标是到达右下角的单元格 (m - 1, n - 1)。
有两种移动方式可用：
- 普通移动：你可以从当前单元格 (i, j) 向右或向下移动，即移动到 (i, j + 1)（右）或 (i + 1, j)（下）。成本为目标单元格的值。
- 传送：你可以从任意单元格 (i, j) 传送到任意满足 grid[x][y] <= grid[i][j] 的单元格 (x, y)；此移动的成本为 0。你最多可以传送 k 次。
返回从 (0, 0) 到达单元格 (m - 1, n - 1) 的 最小 总成本。
示例 1:
输入: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2
输出: 7
解释:
我们最初在 (0, 0)，成本为 0。
当前位置 移动 新位置 总成本
(0, 0) 向下移动 (1, 0) 0 + 2 = 2
(1, 0) 向右移动 (1, 1) 2 + 5 = 7
(1, 1) 传送到(2, 2) (2, 2) 7 + 0 = 7
到达右下角单元格的最小成本是 7。示例 2:
输入: grid = [[1,2],[2,3],[3,4]], k = 1
输出: 9
解释:
我们最初在 (0, 0)，成本为 0。
当前位置 移动 新位置 总成本
(0, 0) 向下移动 (1, 0) 0 + 2 = 2
(1, 0) 向右移动 (1, 1) 2 + 3 = 5
(1, 1) 向下移动 (2, 1) 5 + 4 = 9
到达右下角单元格的最小成本是 9。说明:
- 2 <= m, n <= 80
- m == grid.length
- n == grid[i].length
- 0 <= grid[i][j] <= 10^4
- 0 <= k <= 10
思路
有一个 m x n 的二维矩阵 grid，可以向右/向下移动，每次移动的成本为目标单元格的值。此外，在任意单元格 (i, j)，可以 零成本 传送到任意满足条件 (grid[x][y] <= grid[i][j]) 的单元格 (x, y)。求从 (0, 0) 出发最多传送 k 次到达 (m - 1, n - 1) 的最小成本。
定义 dp[i][j][t] 表示从 (0, 0) 最多传送 t 次到达 (i - 1, j - 1) 的最小成本。如果不传送，dp[i][j][t] = min(dp[i - 1][j][t], dp[i][j - 1][t]) + grid[i - 1][j - 1]，如果传送，需要找到所有元素值大于等于 grid[i - 1][j - 1] 的单元格 (x, y)，取 dp[x][y][t - 1] 的最小值。
代码
/**
* @date 2026-01-28 10:04
*/
public class MinCost3651 {
public int minCost(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int[][][] dp = new int[m + 1][n + 1][k + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
Arrays.fill(dp[i][j], Integer.MAX_VALUE / 2);
}
}
int maxCost = 0;
for (int[] row : grid) {
for (int cost : row) {
maxCost = Math.max(maxCost, cost);
}
}
int[] min = new int[maxCost + 1];
Arrays.fill(min, Integer.MAX_VALUE);
int[] suffixMin = new int[maxCost + 2];
Arrays.fill(suffixMin, Integer.MAX_VALUE);
for (int t = 0; t <= k; t++) {
dp[0][1][t] = -grid[0][0];
dp[1][0][t] = -grid[0][0];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int cost = grid[i - 1][j - 1];
dp[i][j][t] = Math.min(Math.min(dp[i - 1][j][t], dp[i][j - 1][t]) + cost, suffixMin[cost]);
min[cost] = Math.min(min[cost], dp[i][j][t]);
}
}
for (int i = maxCost; i >= 0; i--) {
suffixMin[i] = Math.min(suffixMin[i + 1], min[i]);
}
}
return dp[m][n][k];
}
}
性能
