学步园

这个题。。。。数字三角形啦。。。。

简单的dp，记得当时看dp的时候就是从这里开始的【现在可能也就能明白这一个，T_T】

状态转移方程：d[i,j]=a[i][j]+max{d[i+1][j],d[i+1][j+1]};

刘汝佳的书上有讲的。。。。

AC代码：

#include <cstdio>
#include <cstring>
const int maxn=105;
int t[maxn][maxn];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
    {
        scanf("%d",&t[i][j]);
    }
    for(int i=n-2;i>=0;i--)
        for(int j=0;j<=i;j++)
    {
        if(t[i+1][j]>t[i+1][j+1])
            t[i][j]+=t[i+1][j];
        else
            t[i][j]+=t[i+1][j+1];
    }
    printf("%d",t[0][0]);
}