C++ no extra space , 8ms


  • 0
    S

    class Solution {
    public:

    int minimumTotal(vector<vector<int> > &triangle) {
         
         for(int i=1; i<triangle.size(); i++)
         {
             int lastCol = triangle[i].size() -1;
             triangle[i][0] += triangle[i-1][0];
             triangle[i][lastCol] += triangle[i-1][lastCol-1];
             
             for(int j=1; j< lastCol; j++)
                  triangle[i][j]  += min( triangle[i-1][j-1],triangle[i-1][j] );
         }
         
         vector<int> lastRow = triangle[ triangle.size() -1  ];
         int result = lastRow[0];
         for(int i=1; i<lastRow.size(); i++) result = min(result, lastRow[i]);
         return result;
    }
    

    };


Log in to reply
 

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