Untitled

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
887 B
5
Indexable
Never
 vector<int> s;
    int minimumTotal(vector<vector<int>>& triangle,int row,  int index, int sum){
        //if(triangle.size() == 0)    return ;
        if(triangle.size() == 1){
            s.push_back(triangle[0][0]);
        }
        if(row == triangle.size()){
            s.push_back(sum);
            return 0; 
        }
        
        //sum = sum + triangle[row][index];
        
        int a = minimumTotal(triangle, row+1, index, sum+triangle[row][index]);
        int b = minimumTotal(triangle, row+1, index+1, sum+triangle[row][index]);
        
        return (sum + min(a, b));
        
    }
    
    int minimumTotal(vector<vector<int>>& triangle) {
        minimumTotal(triangle, 0, 0, 0);
        int ans = INT_MAX;
        for(int i = 0; i < s.size(); i++){
            ans = min(ans, s[i]);
        }
        
        return ans;
    }