Minimum Path Sum Matrix

Find the minimum cost path from top-left to bottom-right in a grid.

dynamic-programming matrix path optimization

You are given a 2D grid of non-negative integers. You want to go from the top-left corner to the bottom-right corner, moving only **right** or **down** at each step. Write a function `min_path_sum(grid)` that returns the minimum sum of numbers along such a path.

**Input**: A list of lists of non-negative integers (each cell is between 0 and 10^3). The grid is non-empty and dimensions m x n (1 <= m,n <= 100).

**Output**: An integer, the minimum total sum from (0,0) to (m-1,n-1).

**Note**: You must solve it without using external libraries. The function should be efficient: O(m*n) time is acceptable.

Constraints

1 <= len(grid) <= 100
1 <= len(grid[0]) <= 100
0 <= grid[i][j] <= 1000

Time complexity: O(m*n)
Space complexity: O(m*n) or O(n) is acceptable.

Example

>>> min_path_sum([[1,3,1],[1,5,1],[4,2,1]])
7
>>> min_path_sum([[1,2,3],[4,5,6]])
12
>>> min_path_sum([[5]])
5

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about the minimum number of steps to reach each cell. You can only come from the top or from the left.

Create a dp table where dp[i][j] is the minimum sum to reach cell (i,j). The base case is the top-left cell.

For other cells, the value is the grid value plus the minimum of the top and left neighbor. Watch out for edges.

You can reduce space by only keeping the previous row if you want, but a full 2D DP is fine for the constraints.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.