Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Compute the minimum remaining cost from each cell to the destination, rather than the cost from the start. With one teleport available, a cell of value v may jump freely to any cell valued at most v. A prefix minimum over cell values summarizes all those destinations for the previous teleport budget.

Approach

Initialize remaining costs to infinity and the destination to zero. Process budgets from zero through k. For each budget, scan cells from bottom-right to top-left, relaxing a normal move down or right by adding that neighbor's value to its remaining cost. When the budget is positive, also relax using the previous budget's prefix-minimum teleport cost for the current value.

After completing a layer, group its best costs by grid value and prefix-minimize that array, preparing teleport choices for the next layer. Retaining prior costs represents using at most the budget, so fewer-teleport paths remain available.

Normal moves use the current layer, but teleport moves use only the completed previous layer, preventing extra teleports from leaking into a state. Return the remaining cost at (0, 0); the starting cell's own value is never charged.

class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        n = len(grid)
        m = len(grid[0])
        cost = [[inf] * m for _ in range(n)]
        cost[-1][-1] = 0
        tcost = [inf] * (max(max(row) for row in grid) + 1)

        for t in range(k + 1):
            for i in range(n - 1, -1, -1):
                for j in range(m - 1, -1, -1):
                    if i < n - 1:
                        cost[i][j] = min(cost[i][j], cost[i + 1][j] + grid[i + 1][j])
                    if j < m - 1:
                        cost[i][j] = min(cost[i][j], cost[i][j + 1] + grid[i][j + 1])
                    if t > 0:
                        cost[i][j] = min(cost[i][j], tcost[grid[i][j]])

            for i in range(n):
                for j in range(m):
                    tcost[grid[i][j]] = min(tcost[grid[i][j]], cost[i][j])

            for i in range(1, len(tcost)):
                tcost[i] = min(tcost[i], tcost[i - 1])

        return cost[0][0]

Complexity analysis

Let r and c be the grid dimensions and V = max(grid) + 1. Both implementations build one monotone-path DP layer and then one layer per allowed teleport, taking O((k + 1)(rc + V)) time and O(rc + V) auxiliary space.