Minimum path sum
Given a grid of height
h and width w filled with integers, you are asked to find a path from the top-left to the bottom-right corner that minimizes the sum of numbers along the path. You are only allowed to move right or down.3 | 2 | 1 | 3 |
1 | 9 | 2 | 3 |
9 | 1 | 5 | 4 |
Input
The first line of the input contains two integers
h and w (1 ≤ h, w ≤ 1000).The next
h lines contain w space-separated integers Output
The program should print the minimum possible sum to get from the top-left corner to the bottom-right corner.
Examples
Input | Output |
3 4
3 2 1 3
1 9 2 3
9 1 5 4 | 15 |
Explanation
We can move: 3 → 2 → 1 → 2 → 3 → 4
Hint 1
The state in a dynamic programming problem can be a 2-dimensional array.
Hint 2
It can represent the best possible solution up to that coordinate (
d[r][c] represents the best path to reach the row r and the column c).Why doesn’t the greedy approach work here? Imagine if you always moved in the direction of the smallest possible value. What would be the issue there?
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB