给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        73   88   1   02   7   4   4
4   5   2   6   5

输入格式

第一行包含整数 nn，表示数字三角形的层数。

接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤5001≤n≤500,
−10000≤三角形中的整数≤10000−10000≤三角形中的整数≤10000

输入样例：

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

输出样例：

30

 思路：

        使用的是dp算法，根据闫氏dp算法：

        1.原题的总体思路可以是从上到下，也可以是从下到上。从上到下的话，遍历到每个节点的时候不能保证其一定具有左右父母节点（在边缘的节点只有一个父节点）。而采用从下到上的方法的话，除了叶子结点外，每个节点一定都有左右子节点，这样就能节省代码行数。

        2.首先要确定状态表示。状态表示就要确定集合和表示。这一题要求的是路径上的点的和，因此可以确定集合是坐标的形式，确定为：从下到上进行移动到f[i][j]的所有路径的累加和。而属性易得就是最大值。

        3.然后确定状态计算。状态计算就是：因为每个节点f[i][j]都有自己的左右子节点，因此只需要得到子节点中f[i+1][j]或f[i+1][j+1]的较大值，再加上自身原来的值，就可以得到到达该点所有路径中累加和的最大值。

        因此，代码就是：

        

#include<bits/stdc++.h>
using namespace std;const int N=510,INF=0x3f3f3f3f;
int f[N][N];
int a[N][N];int main(){int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){             for(int j=0;j<=i+1;j++){          //因为有负数，所以应该将两边也设为-INFf[i][j]=-INF;}}f[1][1]=a[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);}}int res=-INF;for(int i=1;i<=n;i++) res=max(res,f[n][i]);cout<<res<<endl;作者：TaoZex
链接：https://www.acwing.com/solution/content/3485/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。