[LeetCode] Minimum Path Sum

Problem Statement (link):

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.

Analysis:
This problem is obviously a DPproblem. We could construct a 2D dp matrix with the same size as given grid, in which entry dp[i][j] represents the minimum path sum from (0, 0) to (i, j). After we initialize the first row and col of dp matrix, we could iteratively adding new min path sums to each entry. The last dp entry is the result we are looking for. This solution is shown in Sol 1 below. The time and space complexity of this algorithm is O(m*n), where m and n are dimension of the grid.

However, using the same idea from the problem Triangle, we could reduce the space complexity to O(n). The idea is to reuse the dp vector each time we reach a new row/col - depending on which one we choose. See Sol 2 for the implementation of this algorithm.

Code:
Sol 1:

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m=grid.size();
        int n=grid[0].size();
        if (m==0) return 0;
        vector<vector<int>> dp(m, vector<int> (n));

        // init dp
        dp[0][0]=grid[0][0];
        for (int i=1; i<m; i++)
            dp[i][0]=grid[i][0]+dp[i-1][0];
        for (int j=1; j<n; j++)
            dp[0][j]=grid[0][j]+dp[0][j-1];

        // traverse
        for (int i=1; i<m; i++)
            for (int j=1; j<n; j++)
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j];
      
        return dp[m-1][n-1];
    }
};

Sol 2:

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int m=grid.size();
        int n=grid[0].size();
        if (m==0) return 0;
        vector<int> dp(n, INT_MAX);
        dp[0]=0;

        // traverse
        for (int i=0; i<m; i++) {
            dp[0]=grid[i][0]+dp[0];
            for (int j=1; j<n; j++)
                dp[j]=min(dp[j], dp[j-1])+grid[i][j];
        }
        return dp[n-1];
    }
};