Passed c++ code, only need O(n) extra space and don't change the original data


  • 7
    L
    int minPathSum(vector<vector<int> > &grid) {
        int rows = grid.size();
        if (rows==0) return 0;
        int cols = grid[0].size();
        vector<int> vi(cols, INT_MAX);
    
        int i, j;
        vi[0] = 0;
        for (i=0; i<rows; i++) {
            vi[0] += grid[i][0];
            for (j=1; j<cols; j++) {
                vi[j] = min(vi[j-1], vi[j])+grid[i][j];
            }
        }
        return vi[cols-1];
    }

  • 0
    N

    How can we modify this code if we are allowed to move in diagonal direction also ?


Log in to reply
 

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