Show problems as
Classic problem #64MediumArrayDynamic ProgrammingMatrix

Minimum Path Sum

Real-world version: Cheapest Bay Route
Tracked in this browser only
Read Minimum Path Sum on LeetCode(opens in a new tab)

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

Learn the pattern firstBasic Dynamic Programming · Dynamic Programming, animated step by step

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

Python
def cheapest_bay_route(fees: list[list[int]]) -> int:
Java
public int cheapestBayRoute(int[][] fees)

More on the same topics