Acwing 898 数字三角形

题目链接：

Acwing 898 数字三角形

例题：

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

思路：

由题可知，要到最后一层的时候，所走的路径之和为最大，那么有两个需求：

第一：是走到最后一层

第二：是求最大的

那么最后一层的结果有很多，如例题有五个节点都是最终结果，而且路径不一样，同一个结果的路径之和也不一样。

有如下图，到达同一个节点，但是由于路径不同，其结果也不同。

步骤：

1. 要先求出最后一层每一个节点的最优解
2. 从最后一层的所有节点的最优解中取最大

第一步：求最后一层每一个节点的最优解（核心）：

比如要求第二个节点的最优解，那么只要保证第四层能够通往他的两个节点是最优解即可：

同理可得，第三层的节点的最优解亦是如此：

由此可以退出状态公式：dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + q[i][j];

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

const int N = 510;

int p[N][N];
int dp[N][N];

int main()
{
    int n;
    cin>>n;
    //初始化
    for(int i = 0; i < N ; i++ )
        for (int j = 0 ; j < N; j ++)
            p[i][j] = dp[i][j] = -10001;
    //输入
    for(int i = 1; i <= n ; i++ )
        for (int j = 1 ; j <= i; j ++)
            cin>>p[i][j];
    //记录状态
    dp[1][1] = p[1][1];
    //递推
    for( int i = 2; i <= n; i ++)
        for( int j = 1; j <= i; j ++)
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]) + p[i][j];
    //从最后一层中寻找最优解
    int res = -10001;
    for(int i = 1; i <= n; i ++)
        res = max(dp[n][i],res);
    cout<<res<<endl;
    return 0;
}