因为上下相加的路线只能存在一条,并且,从上往下选择的话,每种情况都要罗列一遍很轻易的超时,所以我们从下往上选择。
每个分支我们只要加上它可以加上的最大值就可以了
所以最后的时间复杂度大概为 O($n^2$)
实现代码如下
#include<iostream>
using namespace std;
int a[510][501];
int main(){
int n;cin>>n;
for(int i=0;i<n;i++) for(int j=0;j<=i;j++)
cin>>a[i][j];
for(int i=n-1;i;i--) for(int j=0;j<i;j++)
a[i-1][j]+=max(a[i][j],a[i][j+1]);
cout<<a[0][0];
}