dp板子题：

动态规划（DP）问题是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。‌ 拿这题举例，我们要求从顶点到底部路径最大值问题，可以想起分解到求第i层某点到第i+1层某点路径的最长距离。这样逐渐迭代，局部最优解往往会变成全局最优解。

闫式DP分析法：
1. 状态表示（f(i,j)），第一个问题：f(i,j)表示什么？第二个问题：它的属性是什么？（最大值，最小值，计数）从中选一个。
2. 状态计算(集合划分)，思考这些集合可以怎么划分。

用法（拿本题举例）：
1. 求从顶点到底层的最长路径，常规方法是从底层开始往上遍历。因此f(i,j)是底层到f(i,j)所有路径的集合。第二个问题，它的属性是什么？明显本题是想求最长路径问题，现在我们用这个方法迭代f子问题的最优解，从而拼凑出全局最优解。因此这里的f(i,j)是最大值（代表从底层到f(i,j)中的路径集合中的最大值）
2. 然后思考怎么迭代这个f(i,j)到f(1,1)，这时候要思考状态（集合）划分，因为只有把集合划分好，才能用max()求集合中所有路径方案的最优解。从题目中可以看出，一个顶点只有一个左子树和一个右子树，因此只需分成两个集合，左集合和右集合。我们从n-1层开始遍历，[i][j]的左子树是它正下方的元素[i+1][j],右子树是它右下方的元素[i+1][j+1],因此只需要比较[i+1][j]+[i][j] 和[i+1][j+1]+[i][j]，谁大即可。

最后输出最顶点f（1，1）

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int w[N][N];
int n;
int 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];

    //因为待会从倒数第二层开始迭代，需要用到倒数第一层的权值，所以干脆将最后一层的权值赋到f数组中对应的位置中去。
    for(int i = 1 ; i <= n ; i++) f[n][i] = w[n][i];

    for(int i = n-1; i > 0 ; i--)
        for(int j = 1; j <= i ; j++)
            f[i][j] = max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);

    cout << f[1][1];

    return 0;
}