Sharing my 16ms C++ solution


  • 0
    T
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int m = grid.size();
            if(m==0)
                return 0;
            int n = grid[0].size();
            if(n==0)
                return 0;
                
            vector<vector<int>> DP;
            DP.resize(m);
            int i, j;
            for(i=0; i<m; i++)
                DP[i].resize(n);
            
            DP[0][0] = grid[0][0];
            
            for(i=1; i<m; i++)
                DP[i][0] = DP[i-1][0] + grid[i][0];
            for(j=1; j<n; j++)
                DP[0][j] = DP[0][j-1] + grid[0][j];
                
            for(i=1; i<m; i++)
                for(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];
        }
    };

  • 0
    J

    I think the initialization of variable DP can be more concise:

    vector<vector<int>> DP(m, vector<int>(n, 0));

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.