数塔问题

输入

5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4

输出

44

//数塔问题，dp的递推形式
//状态和状态转移方程，
//分为边界，开始的地方就是边界




#include <cstdio> 
#include <iostream>
#include <algorithm>


using namespace std;


const int MAXN=1000;


int f[MAXN][MAXN],dp[MAXN][MAXN];




int main()
{
    //n为层数 
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>f[i][j];

        }
    }


    for(int i=1;i<=n;i++)
    {
        dp[n][i]=f[n][i];

    }



    for( int i=n-1;i>=1;i--)
    {

        for(int j=1;j<=i;j++)
        {

            dp[i][j]=max( dp[i+1][j],dp[i+1][j+1]  )+f[i][j];


        }


    }


    cout<<dp[1][1]<<endl;

    return 0;




}