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] <= 200

4. Solutions

Dynamic Programming

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) {
        const int m = grid.size(), n = grid.front().size();
        vector<int> min_sum_end_at(n, numeric_limits<int>::max());
        min_sum_end_at[0] = 0;
        for (int i = 0; i < m; ++i) {
            min_sum_end_at[0] += grid[i][0];
            for (int j = 1; j < n; ++j) {
                min_sum_end_at[j] = min(min_sum_end_at[j - 1], min_sum_end_at[j]) + grid[i][j];
            }
        }

        return min_sum_end_at.back();
    }
};