1130HardArrayDynamic ProgrammingMatrix

Crossing the Yard With Free Hops

Tracked in this browser only

Trains the technique from

LeetCode 3651Minimum Cost Path with Teleportations

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_cost(grid: list[list[int]], k: int) -> int:

Java

public int minCost(int[][] grid, int k)

The intended approach

Time O(k * (rows * cols + tolls)) over the layers.Space O(rows * cols + tolls) for a layer and the grouping.

Steps only ever go right or down, so with no hops at all the cheapest way to each square is its own toll plus the cheaper of the squares above and to its left. That is one sweep in reading order. Hops change nothing about that sweep, they only change where a run of steps may begin. So build the answer in layers, one per number of hops used. Layer zero is the plain sweep. To move from one layer to the next, work out what it costs to arrive at each square by hopping into it: the hop is free, so the cost is the cheapest cost in the previous layer over all squares whose toll is at least this square's toll. Those arrival costs come out of one pass. Group the previous layer's costs by the toll of their square, keeping the cheapest per toll, then run a smallest-so-far from the highest toll downwards. Reading that off at a square's own toll gives exactly the cheapest place a hop into it could come from, and the direction matters: a hop needs a square of higher or equal toll, never a lower one. Then sweep the new layer in reading order, taking each square as the cheaper of hopping in and stepping in from above or the left within the same layer. Letting steps follow a hop is what makes a square with no possible hop into it still improve. Adding a layer can never make a square dearer, since a square can always hop to itself, so the last layer already holds the answer, and keeping a running best across the layers costs nothing.

Pythonentry point: min_cost

def min_cost(grid, k):
    rows = len(grid)
    cols = len(grid[0])
    inf = 1 << 60
    top = 0
    for row in grid:
        for value in row:
            if value > top:
                top = value
    best = [[inf] * cols for _ in range(rows)]
    best[0][0] = 0
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            reach = inf
            if r and best[r - 1][c] < reach:
                reach = best[r - 1][c]
            if c and best[r][c - 1] < reach:
                reach = best[r][c - 1]
            if reach < inf:
                best[r][c] = reach + grid[r][c]
    answer = best[rows - 1][cols - 1]
    for _ in range(k):
        floor = [inf] * (top + 2)
        for r in range(rows):
            for c in range(cols):
                value = grid[r][c]
                if best[r][c] < floor[value]:
                    floor[value] = best[r][c]
        for value in range(top - 1, -1, -1):
            if floor[value + 1] < floor[value]:
                floor[value] = floor[value + 1]
        step = [[inf] * cols for _ in range(rows)]
        for r in range(rows):
            for c in range(cols):
                entry = floor[grid[r][c]]
                reach = inf
                if r and step[r - 1][c] < reach:
                    reach = step[r - 1][c]
                if c and step[r][c - 1] < reach:
                    reach = step[r][c - 1]
                if reach < inf and reach + grid[r][c] < entry:
                    entry = reach + grid[r][c]
                step[r][c] = entry
        best = step
        if best[rows - 1][cols - 1] < answer:
            answer = best[rows - 1][cols - 1]
    return answer

The obvious version

Treat every combination of square and hops used as a place to be, and walk outwards from the start always taking the cheapest place reached so far. From a place, stepping right or down costs the entered square's toll, and while hops remain every square with a toll no higher is reachable for nothing, listed one at a time. The first time the far corner is drawn out, its cost is settled. Costs the square count squared for every hop allowance.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_cost(grid, k):
    import heapq
    rows = len(grid)
    cols = len(grid[0])
    settled = {}
    heap = [(0, 0, 0, 0)]
    while heap:
        cost, r, c, used = heapq.heappop(heap)
        key = (r, c, used)
        if key in settled:
            continue
        settled[key] = cost
        if r == rows - 1 and c == cols - 1:
            return cost
        if r + 1 < rows:
            heapq.heappush(heap, (cost + grid[r + 1][c], r + 1, c, used))
        if c + 1 < cols:
            heapq.heappush(heap, (cost + grid[r][c + 1], r, c + 1, used))
        if used < k:
            here = grid[r][c]
            for y in range(rows):
                for x in range(cols):
                    if grid[y][x] <= here:
                        heapq.heappush(heap, (cost, y, x, used + 1))
    return -1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in