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
rlines:ctolls 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).