Problem Statement:

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

Constraints:

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

Solution:

The top row and leftmost column can simply be computed. After that for any node, the answer can be either its upward neighbor + node value or its leftward neighbor + node value;

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