DSA problem
Minimum Cost Path with Teleportations
You are given an m x n non-negative grid matrix and an integer k. Starting at (0, 0), reach (m - 1, n - 1) moving only right or down. The cost of stepping onto a cell is its value. In addition you may perform at most k "teleports": at any moment you may pay matrix[r][c] once and instantly teleport from your current cell (r, c) to any other cell (r', c') with (r', c') >= (r, c) (componentwise) for free — that is, a teleport replaces a sequence of right/down steps with a single jump that bypasses their costs but still requires you to pay the source's value. Return the minimum total cost.
This is a layered DP. Let dp[r][c][j] = minimum cost to reach (r, c) having used j teleports already. The transitions are:
(1) Walk transition (cost matrix[r][c] for arriving on the cell): dp[r][c][j] = matrix[r][c] + min(dp[r - 1][c][j], dp[r][c - 1][j]). This mirrors the standard "Minimum Path Sum" recurrence but in a layer indexed by teleports used.
(2) Teleport transition (j > 0): dp[r][c][j] = min(dp[r'][c'][j - 1]) over all (r', c') with r' <= r, c' <= c, (r', c') != (r, c). Naively this scan is O(m * n) per cell, giving O((m * n)^2 * k) overall — usually too slow.
The trick is to maintain a running prefix-min of dp[*][*][j - 1] over the rectangle [0..r][0..c]. After the layer j - 1 is filled, build a 2-D prefix-min prefMin[r][c] in O(m * n). Then each teleport lookup is O(1). Layer j is filled in O(m * n) for the walk transitions plus O(m * n) to update from prefMin. Total: O(k * m * n) time and O(m * n) extra per layer (or O(k * m * n) if you store all layers).
Examples
matrix = [[1,2,3],[4,5,6],[7,8,9]], k = 021matrix = [[1,9,9],[9,9,9],[9,9,1]], k = 111matrix = [[5]], k = 05Constraints
- 1 <= m, n <= 100
- 0 <= matrix[r][c] <= 1000
- 0 <= k <= 5
- Movement is restricted to right or down (one step).
- Each teleport consumes one of the `k` available jumps and replaces a sequence of right/down moves with one free jump.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.