Show problems as
Classic problem #3651HardArrayDynamic ProgrammingMatrix

Minimum Cost Path with Teleportations

Real-world version: Crossing the Yard With Free Hops
Tracked in this browser only
Read Minimum Cost Path with Teleportations on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A yard is laid out as a grid grid, and grid[r][c] is the toll charged for entering that square. A trolley starts on the top-left square and must reach the bottom-right one. The starting square costs nothing.

Two kinds of move are available:

  • A step goes one square right or one square down, and costs the toll of the square entered.
  • A hop goes from the square the trolley stands on to any square whose toll is no higher than the toll of the square it stands on. A hop costs nothing, and at most k hops may be made in total.

Return the smallest total toll for getting from the top-left square to the bottom-right one.

Examples

Example 1

Input
grid = [[1, 2], [3, 4]], k = 0
Output
6

No hops are allowed, so only the order of the steps is open. Going right and then down pays 2 and then 4, which beats going down and then right.

Example 2

Input
grid = [[9, 1], [1, 1]], k = 1
Output
0

The starting square carries the highest toll on the yard, so one hop can land anywhere at all, the far corner included, for nothing.

Example 3

Input
grid = [[5, 5], [5, 100]], k = 1
Output
100

No square carries a toll as high as the far corner, so no hop can land on it. Instead hop from the start onto the square beside it, free because both carry 5, and then step in and pay the corner's 100.

Constraints

  • 2 <= grid.length <= 80
  • 2 <= grid[i].length <= 80
  • 0 <= grid[i][j] <= 10^4
  • 0 <= k <= 10

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_cost(grid: list[list[int]], k: int) -> int:
Java
public int minCost(int[][] grid, int k)

More on the same topics