数字三角形详解

                       数字三角形状态转移方程(由底层向顶层)：
                                  a[i][j]=max(a[i+1][j+1],a[i+1][j])+a[i][j]

（数组a为输入存储数组，n为层数，同时也是列数，a[i][j]表示该点到底层的最大权值之和（即最长路径））
1.由底层向顶层推时最底层到底层的权值是它本身，所以从n-1层开始推
2.n-1层的每个点到底层的最大权值为----该点权值+max(下方点的权值,右下方点的权值)
3.n-2,n-3,n-4层每个点的道理亦是如此，直到推到第一层即是答案

e.g.
    0      i   7
    1      i   3  8
    2      i   8  1  0
    3      i   2  7  4  4
    4      i   4  5  2  6  5
               j  j  j  j  j
               0  1  2  3  4

代码如下：

#include<iostream>
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[n][n]; 
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++)
            cin>>a[i][j];
    }


    for(int i=n-2; i>=0; i--) {
        for(int j=0; j<=i; j++) {
            a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
        }
    }
    cout<<a[0][0];
    return 0;
}