来自CodeVS1220 数字三角形 CodeVS的天梯题目排序这里就不吐槽了，这题最后一题还以为是最难的。实际上就是一大$$H_2O$$题

题目描述 Description

如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。

输入描述 Input Description

第一行是数塔层数N(1<=N<=100)。

第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。

输出描述 Output Description

输出最大值。

样例输入 Sample Input

5

13

11 8

12 7 26

6 14 15 8

12 7 13 24 11

样例输出 Sample Output

86

数据范围及提示 Data Size & Hint
数字三角形
这题是我可能也是大多数人的DP入门第一题。
一个最简单的递推，自下往上不断取最大值。
方程是：
$$f(i,j)=f(i,j)+max\{f(i+1,j),f(i+1,j+1)|i<=n-1,j<=i\}$$
我的代码：
#include<cstdio>
#include<cstring>
int map[101][101],f[101][101],n;
int max(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    scanf("%d",&n);
    memset(map,0,sizeof(map));
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=i;j++)
    {
        scanf("%d",&map[i][j]);
    }
    for(int i=n-1;i>=1;i--)
    for(int j=1;j<=i;j++)
    {
        map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
    }
    printf("%d\n",map[1][1]);
    return 0;
}
<span id="mce_marker" data-mce-type="bookmark" data-mce-fragment="1">​</span>