Cheapest Corner-to-Corner Route

Medium

You are given an m × n table costs of non-negative numbers: the fee for entering each cell. Travel from the top-left cell to the bottom-right one, moving only right or down. The cost of a route is the sum of the numbers in every cell it passes through, the first and last included. Return the lowest possible cost.

Example 1

costs=[[2, 9, 1], [3, 4, 1], [6, 1, 2]] → 12

The route 2 → 3 → 4 → 1 → 2 costs 12; nothing is cheaper.

Example 2

costs=[[5, 0, 0, 7]] → 12

With a single row there is only one route: 5 + 0 + 0 + 7 = 12.

Example 3

costs=[[1, 2], [8, 3], [0, 4]] → 10

Constraints

1 ≤ m, n ≤ 200
0 ≤ costs[i][j] ≤ 200

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Warehouse Cart Routes Medium Largest Solid Square Medium Best Spot for the Turret Medium Steps to the Nearest Zero Medium Longest Lit Line Medium

Input

costs=[[2, 9, 1], [3, 4, 1], [6, 1, 2]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 77 tests on the server, hidden ones included.