Find the minimum sum path from the top-left to the bottom-right of a grid by moving only right or down.
Minimum Path Sum
You are given a 2D grid of non-negative integers. Start at the top-left cell and move to the bottom-right cell. At each step, you may move only right or only down.
Return the minimum possible sum of the values along any valid path, including both the starting and ending cells.
A good solution should avoid exploring all paths directly and instead reuse partial answers from smaller subproblems.
Input Format
- A 2D integer grid
gridwithmrows andncolumns. grid[i][j]is the cost of entering cell(i, j).
Output Format
- Return a single integer: the minimum path sum from
grid[0][0]togrid[m-1][n-1].
Constraints
1 <= m, n- Grid values are non-negative integers.
- You may move only right or down.
- The exact official constraints are not provided here; assume typical interview-scale sizes.
Example 1
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
Explanation
One optimal path is 1 → 3 → 1 → 1 → 1, which sums to 7.
Example 2
Input
grid = [[1,2,3],[4,5,6]]
Output
12
Explanation
The minimum path is 1 → 2 → 3 → 6, with total sum 12.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.