算法1
(贪心算法) $O(n^2)$
时间复杂度
O(n)
参考文献
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n, t, ans;
cin >> n;
vector<vector<int>> num(n);
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
cin >> t;
if(i == 0) num[i].push_back(t);
else if(j > 0){
if(j < i) num[i].push_back(max(num[i - 1][j - 1], num[i - 1][j]) + t);
else num[i].push_back(t + num[i - 1][j - 1]);
}
else num[i].push_back(t + num[i - 1][j]);
if(i == n-1){
if(j == 0) ans = num[i][j];
else if(num[i][j] > ans) ans = num[i][j];
}
// cout << num[i][j] << ' ';
}
// cout << endl;
}
cout << ans << endl;
}