8-lines 12ms Beat 100% O(n)-space DP solution in C++


  • 0
    C
        int m = grid.size(), n = grid[0].size();    
        vector<int> curV(m+1, INT_MAX); 
        curV[0] = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                curV[j+1] = grid[j][i]+min(curV[j+1], curV[j]);
            curV[0] = curV[1];  
            }
        }
        return curV[m];

Log in to reply
 

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