Untitled
unknown
c_cpp
4 years ago
887 B
9
Indexable
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;
}Editor is loading...