Description
You are given a m x n 2D integer array grid and an integer k. You start at the top-left cell (0, 0) and your goal is to reach the bottom‐right cell (m - 1, n - 1).
There are two types of moves available:
-
Normal move: You can move right or down from your current cell
(i, j), i.e. you can move to(i, j + 1)(right) or(i + 1, j)(down). The cost is the value of the destination cell. -
Teleportation: You can teleport from any cell
(i, j), to any cell(x, y)such thatgrid[x][y] <= grid[i][j]; the cost of this move is 0. You may teleport at mostktimes.
Return the minimum total cost to reach cell (m - 1, n - 1) from (0, 0).
Example 1:
Input: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2
Output: 7
Explanation:
Initially we are at (0, 0) and cost is 0.
| Current Position | Move | New Position | Total Cost |
|---|---|---|---|
(0, 0) |
Move Down | (1, 0) |
0 + 2 = 2 |
(1, 0) |
Move Right | (1, 1) |
2 + 5 = 7 |
(1, 1) |
Teleport to (2, 2) |
(2, 2) |
7 + 0 = 7 |
The minimum cost to reach bottom-right cell is 7.
Example 2:
Input: grid = [[1,2],[2,3],[3,4]], k = 1
Output: 9
Explanation:
Initially we are at (0, 0) and cost is 0.
| Current Position | Move | New Position | Total Cost |
|---|---|---|---|
(0, 0) |
Move Down | (1, 0) |
0 + 2 = 2 |
(1, 0) |
Move Right | (1, 1) |
2 + 3 = 5 |
(1, 1) |
Move Down | (2, 1) |
5 + 4 = 9 |
The minimum cost to reach bottom-right cell is 9.
Constraints:
2 <= m, n <= 80m == grid.lengthn == grid[i].length0 <= grid[i][j] <= 1040 <= k <= 10
Solutions
This code solves a minimum cost path problem from the top-left to bottom-right of a 2D grid. It works by sorting all grid cells by their cost values, then running up to k+1 relaxation iterations. In each iteration, it groups cells with identical costs together and propagates the minimum accumulated cost to all cells in each group. After that, it uses dynamic programming working backwards from the bottom-right corner (where the cost is 0) to calculate the cheapest way to reach every other cell by only moving right or down. This relaxation process repeats k times to explore different path possibilities, allowing the algorithm to find the globally optimal minimum cost to reach the top-left starting position. The final answer is the accumulated cost at position [0][0].
/**
* @param {number[][]} grid
* @param {number} k
* @return {number}
*/
function minCost(grid, k) {
const m = grid.length,
n = grid[0].length;
const points = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
points.push([i, j]);
}
}
points.sort((a, b) => grid[a[0]][a[1]] - grid[b[0]][b[1]]);
const costs = Array.from({ length: m }, () =>
Array(n).fill(Number.MAX_SAFE_INTEGER),
);
for (let t = 0; t <= k; t++) {
let minCost = Number.MAX_SAFE_INTEGER;
for (let i = 0, j = 0; i < points.length; i++) {
minCost = Math.min(minCost, costs[points[i][0]][points[i][1]]);
if (
i + 1 < points.length &&
grid[points[i][0]][points[i][1]] ===
grid[points[i + 1][0]][points[i + 1][1]]
) {
continue;
}
for (let r = j; r <= i; r++) {
costs[points[r][0]][points[r][1]] = minCost;
}
j = i + 1;
}
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
if (i === m - 1 && j === n - 1) {
costs[i][j] = 0;
continue;
}
if (i !== m - 1) {
costs[i][j] = Math.min(
costs[i][j],
costs[i + 1][j] + grid[i + 1][j],
);
}
if (j !== n - 1) {
costs[i][j] = Math.min(
costs[i][j],
costs[i][j + 1] + grid[i][j + 1],
);
}
}
}
}
return costs[0][0];
}