Skills101
← All coding problems

Minimum Path Sum

easyDynamic Programming II+10 XPTime limit 2s

A delivery robot crosses a warehouse laid out as an r × c grid. Each cell has a toll. The robot starts at the top-left cell and must reach the bottom-right cell, moving only right or down. It pays the toll of every cell it visits, including the first and the last. Find the minimum total toll.

Input:

  • line 1: r c
  • next r lines: c tolls each

Output: the minimum total toll.

Constraints: 1 ≤ r, c ≤ 300, 0 ≤ toll ≤ 99.

Think about it: the cheapest way to reach a cell comes either from the cell above or the cell on the left: best[i][j] = grid[i][j] + min(best[i−1][j], best[i][j−1]). The first row and column have only one way in. One row of memory is enough.

Sample input 1

3 3
1 3 1
1 5 1
4 2 1

Sample output 1

7

Sample input 2

2 3
1 2 3
4 5 6

Sample output 2

12

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.