A 9ms simple and easy understanding C++ solution


  • 0
    Q
    int minPathSum(vector<vector<int>>& grid) {
        int i = 0, j = 0;
        vector<int> prev(grid[0].size(), 0), curr = prev;
        for (i = 0; i < grid.size(); ++i) {
            for (j = 0; j < grid[i].size(); ++j) {
                if (i == 0 && j == 0)
                    prev[0] = curr[0] = grid[0][0];
                else if (i == 0)
                    prev[j] = curr[j] = curr[j-1] + grid[0][j];
                else if (j == 0)
                    curr[0] = prev[0] + grid[i][0];
                else
                    curr[j] = min(curr[j-1], prev[j]) + grid[i][j];
            }
            prev = curr;
        }
        return curr[j-1];
    }
    

Log in to reply
 

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