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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int minPathSum(const vector<vector<int>> &grid) {
        const int m = grid.size(), n = grid.front().size();
        vector<int> path_sum(n, numeric_limits<int>::max());
        path_sum[0] = 0;
        for (int i = 0; i < m; ++i) {
            path_sum[0] += grid[i][0];
            for (int j = 1; j < n; ++j) {
                path_sum[j] = grid[i][j] + min(path_sum[j - 1], path_sum[j]);
            }
        }

        return path_sum.back();
    }
};