算法
DP
思路
因为从顶部出发到底层的数字的和的最大值其实等于从底层走到顶层的数字的和的最大值(这个很好理解)
既然如此,我们就不妨求一下从底层走到顶层的数字的最大值
由于每一个数字都可以由左下角或右下角的数字走过来,因此,可得动态转移方程式a[i][j]+=max(a[i+1][j],a[i+1][j+1])
而最终a[1][1]中储存的就是从底层走到顶层的数字的和的最大值
c++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+1e2;
ll n;
ll a[N][N];
ll ans;
signed main()
{
cin>>n;
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
for(ll i=n-1;i>=1;i--)//由下往上走
{
for(ll j=1;j<=i;j++)
{
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);//动态转移方程式
}
}
cout<<a[1][1];
return 0;
}