0148MediumArrayDynamic ProgrammingMatrix

Cheapest Bay Route

Tracked in this browser only

Trains the technique from

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 parcel sorting hall is laid out as a rectangular block of bays. You are given fees, where fees[r][c] is the handling fee charged by the bay standing in row r and column c. Fees are never negative and a free bay charges 0.

A parcel is dropped into the bay at row 0, column 0 and must leave from the bay in the final row and final column. From whichever bay the parcel is in, the belt can hand it one bay onwards along the same row, or one bay further down the same column. Nothing carries the parcel backwards along a row or back up a column.

Every bay the parcel passes through charges its fee, and that includes the bay it was dropped into and the bay it leaves from. Return the smallest total fee that any legal routing of the parcel can be billed at.

Examples

Example 1

Input: fees = [[2, 0, 4], [5, 1, 1], [3, 7, 2]]
Output: 6

Routing across the top two bays, then down the middle column and out gives 2 + 0 + 1 + 1 + 2 = 6, and no routing is billed less.

Example 2

Input: fees = [[1, 3, 1, 2], [4, 2, 8, 1]]
Output: 8

Staying in the upper row until the final column and only then dropping down bills 1 + 3 + 1 + 2 + 1 = 8. Cutting down early runs into the bay charging 8.

Example 3

Input: fees = [[9]]
Output: 9

With a single bay the parcel is dropped in and leaves from the same bay, so its fee is billed once.

Constraints

rows == fees.length
cols == fees[r].length
1 <= rows, cols <= 200
0 <= fees[r][c] <= 200

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 cheapest_bay_route(fees: list[list[int]]) -> int:

Java

public int cheapestBayRoute(int[][] fees)

The intended approach

Time O(rows * cols)Space O(cols)

The cheapest way to reach a bay is its own fee plus the cheaper of the two cheapest-ways to reach the bay to its left and the bay above it, because those are the only two bays the belt can arrive from. Settle the top row as running totals, then sweep row by row keeping one array of cheapest-way values: as the sweep reaches a column, the entry still holds the value for the bay above while the entry just written holds the value for the bay to the left, so a single array is enough.

Pythonentry point: cheapest_bay_route

def cheapest_bay_route(fees):
    # Time: O(rows * cols) -- every bay is settled exactly once.
    # Space: O(cols) -- one rolling row of cheapest-way totals.
    cols = len(fees[0])
    best = [0] * cols
    running = 0
    for c in range(cols):
        running += fees[0][c]
        best[c] = running
    for r in range(1, len(fees)):
        best[0] += fees[r][0]
        for c in range(1, cols):
            left = best[c - 1]
            above = best[c]
            best[c] = fees[r][c] + (left if left < above else above)
    return best[cols - 1]

The obvious version

Walk out every legal routing of the parcel with plain recursion, totalling the fees along each one and keeping the smallest total seen. Exponential in the size of the block.

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_cheapest_bay_route(fees):
    rows = len(fees)
    cols = len(fees[0])
    cheapest = [None]

    def walk(r, c, billed):
        billed += fees[r][c]
        if r == rows - 1 and c == cols - 1:
            if cheapest[0] is None or billed < cheapest[0]:
                cheapest[0] = billed
            return
        if c + 1 < cols:
            walk(r, c + 1, billed)
        if r + 1 < rows:
            walk(r + 1, c, billed)

    walk(0, 0, 0)
    return cheapest[0]

How this problem was checked

Reference solution executed against 12 test cases — 12 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