Minimum Path Sum
Beginner
grid holds non-negative numbers. Move right or down from the top-left to the bottom-right cell. Return the smallest possible sum of the numbers on the path (both ends included). An empty grid gives 0.
For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7 (1 + 3 + 1 + 1 + 1).
The starter code is a plain recursion. It is correct but too slow for big grids.
Examples
Example 1
Input:
min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])
Output:
7
Example 2
Input:
min_path_sum([[1, 2, 3], [4, 5, 6]])
Output:
12
Constraints
0 <= rows, cols <= 5000 <= grid[r][c] <= 100
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programminggrid-dp
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.