Medium
Minimum Path Sum
Medium
0 submissions
25 coins
+100 XP
Array
Dynamic Programming
Matrix
Problem Description
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.
**Example 1:**
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.
**Example 2:**
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: Path is 1 -> 2 -> 3 -> 6 = 12.
**Example 3:**
Input: grid = [[1]]
Output: 1
**Hint:** Use dynamic programming: `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`. Handle boundary rows and columns carefully.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200
Need help?
Connect with expert programmers for real-time collaborative coding, video meetings, and whiteboard sessions via CodeConnect.
Video Call
Whiteboard
Live Coding
Screen Share