Recursive in-place solution


  • 0
    V
    int minimumTotal(vector<vector<int>>& triangle) {
            int minSum = 10000;
            if(triangle.size() == 0) return 0;
            if(triangle.size() == 1) return triangle[0][0];
            minTotal(triangle, 1, minSum);
            return minSum;
        }
        
        void minTotal(vector<vector<int>>& triangle, int row, int& minSum){
            
            for(int j = 0; j < triangle[row].size(); j++){
                if(j==0){ 
                    triangle[row][j] += triangle[row-1][j]; // left corner
                }else if(j == triangle[row].size() - 1){
                    triangle[row][j] += triangle[row-1][j-1]; // right corner
                }else{
                    triangle[row][j] += min(triangle[row-1][j-1], triangle[row-1][j]);
                }
            }
            
            if(row == triangle.size()-1){
                for(int j = 0; j < triangle[row].size(); j++){
                    if(minSum > triangle[row][j]) minSum = triangle[row][j];
                }
                return;
            }
            
            minTotal(triangle, row+1, minSum);
        }

Log in to reply
 

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