Link to Question

MEDIUM

Minimum Path Sum

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

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.

---

Constraints

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 200
• 0 ≤ grid[i][j] ≤ 100

---

Solution: Dynamic Programming

• Time Complexity: O(mn)
• Space Complexity: O(n)

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, 0);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) dp[j] = grid[i][j];
                else if (i == 0) dp[j] = dp[j-1] + grid[i][j];
                else if (j == 0) dp[j] = dp[j] + grid[i][j];
                else dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
            }
        }
        return dp[n-1];
    }
};