思路
因为每个上面的数字可以对下面的两个造成影响,所以就自下而上分析:下面两个对上面一个造成影响。
(我觉得实际上是自上而下,后面输入的是上面,看个人理解吧)
C++ 代码
#include<iostream>
using namespace std;
const int N=510;
int a[N][N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
for(int i=n-1;i>=1;i--)
{
for(int j=1;j<=i;j++)
{
a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
}
}
cout<<a[1][1];
return 0;
}