Minimum Path Sum in Grid
MediumPractice library · +20 XPmatrixdynamic programmingbfs
Given a grid of non-negative integers, find a path from the top-left cell to the bottom-right cell that minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.
Input
The first line contains two integers R and C, the number of rows and columns in the grid. The next R lines each contain C integers, representing the grid values.
Output
Print a single integer, the minimum path sum.
Constraints
1 <= R, C <= 1000. Grid values are between 0 and 100.
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
3 3 1 3 1 1 5 1 4 2 1
Output
7
The path 1→3→1→1→1 sums to 7.
Example 2
Input
2 4 1 2 3 4 5 6 7 8
Output
18
The path 1→2→3→4→8 sums to 18.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
3 3 1 3 1 1 5 1 4 2 1
Example 2 input
2 4 1 2 3 4 5 6 7 8