Back to Problems

Minimum Path Sum

Medium
dynamic-programming

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Recurrence Relation: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

The minimum cost to reach cell (i,j) is the value at that cell plus the minimum of the costs to reach the cell above or the cell to the left.

This is a natural extension of the Unique Paths problem, adding cost optimization.

Example 1

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2

Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: The path 1 -> 2 -> 3 -> 6 gives sum 12.

Example 3

Input: grid = [[1,2],[1,1]]
Output: 3
Explanation: The path 1 -> 1 -> 1 gives sum 3.

Constraints

  • •m == grid.length
  • •n == grid[i].length
  • •1 <= m, n <= 200
  • •0 <= grid[i][j] <= 200
Show Hints (4)
Hint 1: At each cell, you can only come from above or from the left.
Hint 2: The minimum path sum to reach (i,j) includes the cell value plus the minimum of paths from above and left.
Hint 3: Handle the first row and column specially - they have only one path.
Hint 4: You can optimize space by modifying the grid in-place or using a 1D array.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?