Navigating a grid is a classic coding challenge, but adding teleportation changes the game entirely. This problem asks us to find the most efficient route when we can either pay to move or jump for free under specific conditions. By mastering this, you will learn how to layer dynamic programming to handle multiple "states" of a problem.
Problem Summary
You're given:
- A 2D grid of size where each cell contains a cost.
- An integer , representing the maximum number of times you can teleport.
- Two movement rules: standard moves (right or down) which cost the value of the destination cell, and teleportation (to any cell with a value less than or equal to your current cell) which costs zero.
Your goal:
- Calculate the minimum total cost to travel from the top-left cell to the bottom-right cell .
Intuition
The core of this problem lies in balancing standard movement and the limited resource of teleports.
- Standard DP: Without teleports, this is a standard pathfinding problem. The cost to reach a cell is the cell's value plus the minimum cost of reaching the cell above it or to its left.
- Teleportation Logic: Teleporting is powerful because it costs . However, you can only teleport to a cell if . This means if we have used teleports to reach a cell with value , we can start a new path from any cell with value with a cost of for that jump.
-
Layered Approach: We solve the problem in "rounds" based on the number of teleports used. For each round from to , we update our minimum costs. We maintain a suffix minimum array (
suf_min_f) that stores the cheapest way to reach any cell that has a value of at least . This allows us to quickly check if teleporting to a cell with value is cheaper than walking to it.
Walkthrough: Understanding the Examples
Example 1: grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2
- Start: We begin at . Initial cost is .
- Move Down: Move to . Cost becomes .
- Move Right: Move to . Cost becomes .
- Teleport: The value at is . We can teleport to because its value is also (and ).
- Cost: The teleportation cost is . Total cost remains .
- Result: Since is the destination, the answer is .
Code Blocks
C++
class Solution {
public:
int minCost(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
// Edge case: if we can teleport and start is >= end, cost can be 0
if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) {
return 0;
}
int mx = 0;
for (auto& row : grid) {
for (int val : row) mx = max(mx, val);
}
vector<int> suf_min_f(mx + 2, 2e9);
vector<int> min_f(mx + 1);
vector<int> f(n + 1);
for (int t = 0; t <= k; t++) {
fill(min_f.begin(), min_f.end(), 2e9);
fill(f.begin(), f.end(), 2e9);
// Initial position adjustment for DP
f[1] = (t == 0) ? 0 : f[1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = grid[i][j];
// Option 1: Walk from top/left. Option 2: Teleport here.
int standard_move = min(f[j], f[j + 1]) + x;
if (i == 0 && j == 0 && t == 0) standard_move = 0;
f[j + 1] = min(standard_move, suf_min_f[x]);
min_f[x] = min(min_f[x], f[j + 1]);
}
}
// Update suffix minimums for the next teleport round
vector<int> prev_suf = suf_min_f;
suf_min_f[mx + 1] = 2e9;
for (int i = mx; i >= 0; i--) {
suf_min_f[i] = min(suf_min_f[i + 1], min_f[i]);
}
if (suf_min_f == prev_suf) break;
}
return f[n];
}
};
Python
class Solution:
def minCost(self, 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 = 0
for row in grid:
mx = max(mx, max(row))
inf = float('inf')
suf_min_f = [inf] * (mx + 2)
f = [inf] * (n + 1)
for t in range(k + 1):
min_f = [inf] * (mx + 1)
new_f = [inf] * (n + 1)
if t == 0:
new_f[1] = 0 # Starting point cost is 0
for i in range(m):
for j in range(n):
x = grid[i][j]
# Compare coming from left/up vs. teleporting
standard_move = min(new_f[j], new_f[j + 1]) + x
if i == 0 and j == 0 and t == 0:
standard_move = 0
new_f[j + 1] = min(standard_move, suf_min_f[x])
min_f[x] = min(min_f[x], new_f[j + 1])
f = new_f
# Prepare suffix minimums for next k iteration
new_suf = [inf] * (mx + 2)
for i in range(mx, -1, -1):
new_suf[i] = min(new_suf[i + 1], min_f[i])
if suf_min_f == new_suf:
break
suf_min_f = new_suf
return f[n]
JavaScript
/**
* @param {number[][]} grid
* @param {number} k
* @return {number}
*/
var minCost = function(grid, k) {
const m = grid.length;
const n = grid[0].length;
if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;
let mx = 0;
for (let row of grid) {
for (let val of row) mx = Math.max(mx, val);
}
const INF = Number.MAX_SAFE_INTEGER;
let sufMinF = new Array(mx + 2).fill(INF);
let f = new Array(n + 1).fill(INF);
for (let t = 0; t <= k; t++) {
let minF = new Array(mx + 1).fill(INF);
let nextF = new Array(n + 1).fill(INF);
if (t === 0) nextF[1] = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const x = grid[i][j];
let standardMove = Math.min(nextF[j], nextF[j + 1]) + x;
if (i === 0 && j === 0 && t === 0) standardMove = 0;
nextF[j + 1] = Math.min(standardMove, sufMinF[x]);
minF[x] = Math.min(minF[x], nextF[j + 1]);
}
}
f = nextF;
let nextSuf = new Array(mx + 2).fill(INF);
for (let i = mx; i >= 0; i--) {
nextSuf[i] = Math.min(nextSuf[i + 1], minF[i]);
}
if (JSON.stringify(sufMinF) === JSON.stringify(nextSuf)) break;
sufMinF = nextSuf;
}
return f[n];
};
Key Takeaways
- State Expansion: Adding a variable like (number of teleports) often means we need to repeat our logic times or add a dimension to our DP table.
- Suffix Minimums: Using an auxiliary array to track the minimum value across a range (like all values ) is a common trick to optimize search time from to .
- Space Optimization: We only ever need the results from the "previous teleport count" to calculate the "current teleport count," allowing us to save memory.
Final Thoughts
This problem is a fantastic representation of how real-world logistics systems work. Think of a delivery drone. It can drive along streets (standard moves with cost), but it might also have the battery to fly (teleport) between high-altitude landing pads. Systems like Google Maps or airline routing use similar multi-state optimizations to find the cheapest or fastest paths.
Top comments (0)