Funcia
Lv.2dpgrid

Minimum Toll Path

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A town map is divided into an H×WH \times W grid grid; passing through cell (i, j) costs a toll of grid[i][j].

A traveller starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (H-1, W-1), moving only right or down one cell at a time. Return the minimum possible sum of tolls of all visited cells, including the start and the end.

Examples

gridresult
[[1, 3, 1], [1, 5, 1], [4, 2, 1]]7
[[1, 2, 3], [4, 5, 6]]12
[[5]]5

Example 1 — Right, right, down, down: 1 + 3 + 1 + 1 + 1 = 7.

Example 2 — Along the top row, then down: 1 + 2 + 3 + 6 = 12.

Example 3 — The start is also the destination.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(grid: int[][]) → int

Constraints

  • 1≤H≤7001 \le H \le 700, 1≤W≤7001 \le W \le 700 (grid is an H×WH \times W rectangle)
  • 0≤0 \le grid[i][j] ≤9,999\le 9{,}999

Expected complexity

Time
O(HW)
Space
O(W)

Examples

gridExpected
[[1,3,1],[1,5,1],[4,2,1]]7
[[1,2,3],[4,5,6]]12
[[5]]5

Hint

Hint

A cell can only be entered from above or from the left, so best[i][j] = grid[i][j] + min(best[i-1][j], best[i][j-1]) (the first row and column have a single predecessor). Following every path recursively explores (H+W−2H−1)\binom{H+W-2}{H-1} paths; filling the table row by row is O(HW)O(HW) and one row of memory is enough.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251040 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.