Problems / Minimum Path Sum
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