LeetCode 3651 - Minimum Cost Path with Teleportations

The problem asks us to find the minimum cost to travel from the top-left corner (0, 0) of a 2D grid to the bottom-right corner (m - 1, n - 1). Each cell contains a non-negative integer representing its cost. There are two ways to move: 1.

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 3651

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem asks us to find the minimum cost to travel from the top-left corner (0, 0) of a 2D grid to the bottom-right corner (m - 1, n - 1). Each cell contains a non-negative integer representing its cost. There are two ways to move:

  1. Normal move: move either right or down, paying the value of the destination cell.
  2. Teleportation: jump to any other cell with a value less than or equal to your current cell's value, at zero cost. Teleportation is limited to at most k times.

The input consists of the grid (a 2D array of size m x n) and the integer k. The output is a single integer representing the minimum total cost from start to finish.

Constraints tell us that m and n are small (up to 80), the cell values are moderate (up to 10,000), and the number of teleportations is very limited (0 to 10). This suggests that a brute-force solution exploring all possible paths would be infeasible, especially considering the exponential number of possible teleportation choices.

Important edge cases include:

  • k = 0, meaning no teleportations are allowed.
  • A grid where teleportation may not help at all.
  • A grid where multiple optimal teleportations exist.
  • Smallest grids (2 x 2) to ensure basic movements are handled.

The problem guarantees valid grid dimensions and non-negative values, so we do not need to handle invalid inputs.

Approaches

Brute Force

A brute-force approach would attempt every possible path from (0, 0) to (m - 1, n - 1), trying all combinations of right, down, and teleportation moves. Each path would be evaluated for cost, and we would return the minimum. While this guarantees correctness, the number of paths grows exponentially with m and n and with the choice of teleportation cells. Given the constraints, this approach is computationally infeasible.

Optimal Approach

The key insight is that we can use dynamic programming with teleportation states combined with BFS or Dijkstra-style traversal. We maintain a DP table dp[i][j][t] representing the minimum cost to reach cell (i, j) using at most t teleportations. We then iterate through the grid, updating cells with normal moves and efficiently applying teleportation moves using sorting by value to ensure only valid teleportation targets are considered.

This reduces the exponential search space to a manageable size, leveraging the limited k (≤ 10) and the grid size (≤ 80 x 80). Essentially, we compute minimum costs in layers of teleportations.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n) * combinations of teleportation) O(2^(m+n) * combinations of teleportation) Enumerates all paths including teleportation
Optimal O(m * n * k * log(m * n)) O(m * n * k) Uses DP with teleportation layers and efficient value sorting

Algorithm Walkthrough

  1. Initialize a 3D DP array dp[i][j][t] with infinity, where i and j are coordinates and t is the number of teleportations used. Set dp[0][0][0] = 0.
  2. Preprocess all grid cells into a list of (value, i, j) and sort ascending by value. This allows us to quickly identify valid teleportation targets.
  3. Iterate through t from 0 to k. For each cell (i, j):

a. Update dp[i+1][j][t] and dp[i][j+1][t] for normal moves, ensuring indices stay in bounds.

b. If t < k, consider teleportation. All cells (x, y) with grid[x][y] <= grid[i][j] can be reached at zero additional cost. Update dp[x][y][t+1] as min(dp[x][y][t+1], dp[i][j][t]). 4. After processing all teleportations, return the minimum value among dp[m-1][n-1][0..k], representing the minimum cost to reach the destination using up to k teleportations.

Why it works: By iteratively computing the minimum cost to reach each cell with a given number of teleportations, we maintain the invariant that dp[i][j][t] always contains the optimal cost using exactly t teleportations. Sorting cells by value ensures we only teleport to valid targets.

Python Solution

from typing import List
import heapq

class Solution:
    def minCost(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        INF = float('inf')
        dp = [[[INF] * (k + 1) for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = 0
        
        cells = [(grid[i][j], i, j) for i in range(m) for j in range(n)]
        cells.sort()
        
        for t in range(k + 1):
            for value, i, j in cells:
                # normal moves
                if i + 1 < m:
                    dp[i+1][j][t] = min(dp[i+1][j][t], dp[i][j][t] + grid[i+1][j])
                if j + 1 < n:
                    dp[i][j+1][t] = min(dp[i][j+1][t], dp[i][j][t] + grid[i][j+1])
                
                # teleportation
                if t < k:
                    for value2, x, y in cells:
                        if value2 <= value:
                            dp[x][y][t+1] = min(dp[x][y][t+1], dp[i][j][t])
                        else:
                            break
        
        return min(dp[m-1][n-1])

This implementation follows the DP + teleportation layers strategy. The sorted cells list ensures teleportation updates are valid and efficient. Normal moves update the DP table in place, while teleportation layers propagate costs without exceeding k.

Go Solution

import "math"

func minCost(grid [][]int, k int) int {
    m, n := len(grid), len(grid[0])
    INF := math.MaxInt32
    dp := make([][][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([][]int, n)
        for j := 0; j < n; j++ {
            dp[i][j] = make([]int, k+1)
            for t := 0; t <= k; t++ {
                dp[i][j][t] = INF
            }
        }
    }
    dp[0][0][0] = 0
    
    type Cell struct { val, x, y int }
    cells := make([]Cell, 0, m*n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            cells = append(cells, Cell{grid[i][j], i, j})
        }
    }
    
    // sort cells by value ascending
    sort.Slice(cells, func(a, b int) bool { return cells[a].val < cells[b].val })
    
    for t := 0; t <= k; t++ {
        for _, cell := range cells {
            i, j := cell.x, cell.y
            
            // normal moves
            if i+1 < m {
                dp[i+1][j][t] = min(dp[i+1][j][t], dp[i][j][t] + grid[i+1][j])
            }
            if j+1 < n {
                dp[i][j+1][t] = min(dp[i][j+1][t], dp[i][j][t] + grid[i][j+1])
            }
            
            // teleportation
            if t < k {
                for _, c := range cells {
                    if c.val <= cell.val {
                        dp[c.x][c.y][t+1] = min(dp[c.x][c.y][t+1], dp[i][j][t])
                    } else {
                        break
                    }
                }
            }
        }
    }
    
    ans := INF
    for t := 0; t <= k; t++ {
        if dp[m-1][n-1][t] < ans {
            ans = dp[m-1][n-1][t]
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b { return a }
    return b
}

Go differences: We must explicitly initialize the 3D slice with INF. We use sort.Slice to order cells by value and helper function min to simplify comparisons.

Worked Examples

Example 1

Grid:

1 3 3
2 5 4
4 3 5

k = 2

Step-by-step:

  1. Start at (0,0) cost=0.
  2. Move down to (1,0) cost=0+2=2.