简单动态规划递推思想，两个二维数组轻松拿下

解题思路:

1. 层数的范围<=1000，且走到一个点的最大值与走到更后面的最大值无关（即无后效性），可考虑开二维数组动态规划递推。

2. 走到任意一点（i，j）累积的最大值可视为(i-1,j-1)或(i-1,j)的最大值与该位置的和。

3. 设置两个二维数组拉满[1005][1005],a存储该位置值，b存储从开头到给位置累计最大值。

4. 每一个b[i][j]=max(b[i-1][j],b[i-1][j-1])+a[i][j];

5. 最后过一遍b的最后一行（即b[N][i]),找到最大值输出即为答案。

参考代码：

#include

using namespace std;

int N,a[1005][1005],b[1005][1005]; //定义数组与总行数 

int ans=-2;                                      //题目仅给出各店为非负数，防止特殊情况，将ans设为负数 

int main()

{

cin>>N;

for(int i=1;i<=N;i++)

{

for(int j=1;j<=i;j++)

{

cin>>a[i][j];

}

}                                                      //输入 

b[1][1]=a[1][1];                              //先将第一个b[1][1]赋值 

for(int i=2;i<=N;i++)                    //从第二行开始 

{

for(int j=1;j<=i;j++)

{

b[i][j]=max(b[i-1][j],b[i-1][j-1])+a[i][j];   //每一个位置找最大累加和 

}

}

for(int i=1;i<=N;i++)

{

ans=max(ans,b[N][i]);

}                                                  //搜索b的最后一行，找最大值，即为答案 

cout<<ans<<endl;

    return 0;

}