Simple DP solution 12ms best submission in C++


  • 1

    Instead of handling so many corner cases like this post, which can be tedious. Here is my clean solution, which is rather simple though little bit redundant.

    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) 
        {
            int rowSize = grid.size();
            if(!rowSize) return 0;
            int colSize = grid[0].size();
            for(int r = rowSize-2; r >= 0; --r) grid[r][colSize-1] += grid[r+1][colSize-1];
            for(int c = colSize-2; c >= 0; --c) grid[rowSize-1][c] += grid[rowSize-1][c+1];
            for(int r = rowSize-2; r >= 0; --r)
            {
                for(int c = colSize-2; c >= 0; --c)
                    grid[r][c] += min(grid[r+1][c], grid[r][c+1]);
            }
            return grid[0][0];
        }
    };

Log in to reply
 

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