64. Minimum Path Sum

1. 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.

2. Example

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

3. Constraints

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

4. Solutions

My Accepted Solution

m = grid.size(), n = grid[0].size()
Time complexity : O(mn)
Space complexity : O(n)

class Solution {
public:
    int minPathSum(const vector<vector<int>> &grid) {
        auto dp = grid[0]; // dp[i] means min path sum to i-th element
        for (int i = 1; i < dp.size(); ++i) {
            dp[i] += dp[i - 1];
        }

        for (int i = 1; i < grid.size(); ++i) {
            dp[0] += grid[i][0];
            for (int j = 1; j < dp.size(); ++j) {
                dp[j] = grid[i][j] + min(dp[j - 1], dp[j]);
            }
        }

        return dp.back();
    }
};