Number Triangles chapter 1.5

 开始想着dfs，果断还是超时，看网上是最简单的dp...压力山大

/*

ID: hubiao cave

PROG: numtri

LANG: C++

*/




#include<iostream>
#include<fstream>
#include<string>

using namespace std;

int tr[1002][1002];
int dp[1002][1002];

int gRow;

int dfs(int row,int column);

int main()

{

    ifstream fin("numtri.in");
    ofstream fout("numtri.out");
    int row;
    fin>>row;
    gRow=row;
    for(int i=1;i<=row;i++)
    {
        for(int j=1;j<=i;j++)
        {
            fin>>tr[i][j];
            if(i==row)
                dp[i][j]=tr[i][j];
        }
    }

    for(int i=row-1;i>=1;i--)
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i+1][j]+tr[i][j],dp[i+1][j+1]+tr[i][j]);
        }
    fout<<dp[1][1]<<endl;
    //fout<<dfs(1,1)<<endl;

    return 0;


}

int dfs(int row,int column)
{
    if(row<gRow)
    {
        int t1,t2;
        t1=dfs(row+1,column)+tr[row][column];
        t2=dfs(row+1,column+1)+tr[row][column];
        return t1>t2?t1:t2;
    }
    return tr[row][column];
}