Minimum Cost Path with Teleportations
You are given an 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)or(i + 1, j). 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 is0. You may teleport at mostktimes.
Return the minimum total cost to reach cell (m - 1, n - 1) from (0, 0).
Example 1
1 3 3 2 5 4 4 3 5
Input
grid = [[1,3,3],[2,5,4],[4,3,5]], k = 2Output
7Moving down to
(1, 0), right to (1, 1), then teleporting to (2, 2) gives a minimum total cost of 7.Example 2
1 2 2 3 3 4
Input
grid = [[1,2],[2,3],[3,4]], k = 1Output
9The minimum path moves down to
(1, 0), right to (1, 1), then down to (2, 1) for a total cost of 9.Constraints
- 2 <= m, n <= 80
- m == grid.length
- n == grid[i].length
- 0 <= grid[i][j] <= 10^4
- 0 <= k <= 10