简单的dp题（898.数字三角形）

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。738810274445265输入格式第一行包含整数n，表示数字三角形的层数。接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。输出格式输出一个整数，表示最大的路径数字和。数据范围1 ≤ n ≤ 500−10000≤三角形中的整数≤10000输入样例：573 88 1 02 7 4 44 5 2 6 5输出样例：30代码：（C++）#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N=510;int n,w[N][N],f[N][N];int main(){    cin>>n;//读入层数 for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){            cin>>w[i][j];//读入w[N][N]数组 } }    for(int i=1;i<=n;i++) f[n][i]=w[n][i];//读入f[n][i]for(int i=n-1;i;i--){ for(int j=1;j<=i;j++){ f[i][j]=max(f[i+1][j],f[i+1][j+1])+w[i][j];//逐层返回找最大 } }cout << f[1][1] << endl;//输出求和至顶点的结果 f[1][1] = 30return 0;}解析：题目给的数字三角形测试样例为5*5，从第4行到最后一行有8次选择，因为自上而下是要么wf[i+1][j]，要么w[i+1][j+1]，对于1来说它只能由3、8推算，但对于0来说只能从8推算而不能从w[2][3]推算，这个时候需要判断边界，这就涉及到了边界问题（不太会处理）。而逆推一下，从4，5，2，6，5开始往上走，就不用讨论边界，因为每一个数字w[i][j]都必然从w[i+1][j]或者w[i+1][j+1]推算而来。所以我们只需要先把最后一行读入f[N][N]数组，这样可以解决掉未先读入n行时出现的来源问题，即避免判断第n行是否由第n+1行数据进行下一步比较推得。然后根据n-1行的数据进行max（a,b）比值就能顺利解决此问题。进行循环后最终的f[1][1]一定就是我们所要的最终结果。738810274445265