思路介绍

本题的陷阱在于限制条件，向左下和右下的次数之差不能大于1，但是并没有限定在路程中任意一点向左下和向右下的次数之差，因此到最后一行时，根据此此条件可以计算出总共向右的运动次数，也就是说可以锁定要求的是最后一行中哪个数的最大值，代码如下，与原始数字三角形问题相比，只修改了最后输出数据的选择。还是n2的复杂度，求赞

#include<iostream>
#include<algorithm>


using namespace std;

const int N=110;

int n;
int s[N][N];
int f[N][N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        cin>>s[i][j];
    }
    f[1][1]=s[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+s[i][j];
        }
    }
    if(n%2==0)
    {
        cout<<max(f[n][(n-1)/2+1],f[n][(n-1)/2+2]);
    }
    else
    {
        cout<<f[n][(n-1)/2+1];
    }
    return 0;
}