c++ solution


  • 0
    B
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n=triangle.size();
            int ans=INT_MAX;
            vector<int> result(n,0);
            
            result[0]=triangle[0][0];
            
            for(int i=1;i<n;i++){
                result[i]=result[i-1]+triangle[i][i]; 
                // from back to front, otherwise the front will be replaced
                for(int j=i-1;j>0;j--){
                    result[j]=min(result[j-1],result[j])+triangle[i][j];
                }
                result[0]+=triangle[i][0];
            }
            
            for(int i:result) ans=min(ans,i);
            return ans;
        }
    };
    

Log in to reply
 

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