摘桃子（YOJ2.0中的题）

猜猜看我们老师给这个题的标签是啥

递归回溯

而且难度还是在所有题中最难的（名义上，难度最高是6），刚开始我是想用递归来解的，虽然猴子是从下往上爬，但是从上往下递归解也是可以的

然后我就感觉不对劲了，这不是可以用动态规划来秒杀吗？

从最底下往上一层的那一层开始算，从第一个数开始，加上下面一层可能到达这个位置的两个数中最大的那一个（这样到达这个数的时候，这个位置的数就是一定要到达这个位置的路径中最大的），然后一直运算到最后一个，接着上一层一样逻辑的运算

到了最高一层就是最大的那个数（可以用例子试一下）

这不比递归的计算量低得多？

代码如下：

#include<stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    int tree[n][n];
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= i; j++)
            scanf("%d", &tree[i][j]);
    
    for(int i = n - 2; i >= 0; i--)
        for(int j = 0; j <= i; j++)
            tree[i][j] += (tree[i + 1][j] > tree[i + 1][j + 1]) ? tree[i + 1][j] : tree[i + 1][j + 1];
    
    printf("%d", tree[0][0]);

    return 0;
}

短小精悍

我简直就是秒杀了这一题，笑稀了