DjvuLee

//@pku 1163 DY问题
//最基础的DY问题,采用的是备忘录方式
//在max(dp(r+1,c),dp(r+1,c+1))处错写成了max(s[r+1][c],s[r+1][c+1]),导致了调试时间。
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;

#define N 120
#define fin cin

int v[N][N];
int s[N][N];
int n;
int dp(int r, int c);//adopt the memoization method
int main()
{
    //ifstream fin("input.txt");
    while(fin>>n){
        for(int i=1;i<=n;i++)//read the data
            for(int j=1;j<=i;j++)
                fin>>v[i][j];
        memset(s,-1,sizeof(s));//intialize the sum
        cout<<dp(1,1)<<endl;
    }//end while
    return 0;
}

int dp(int r, int c)//adopt the memoization method
{
    if(r==n)//is the lastest line
        return s[r][c]=v[r][c];
    if(s[r][c]!=-1)//has been caluated
        return s[r][c];
    else
        return s[r][c]=v[r][c]+max(dp(r+1,c),dp(r+1,c+1));
}

//pku 1163 DY 问题
//采用的是迭代的方式
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;

#define N 120
#define fin cin
int v[N][N];
int s[N];

int main()
{
    //ifstream fin("input.txt");
    int n;
    while(fin>>n){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                fin>>v[i][j];
    
        for(int i=1;i<=n;i++)
            s[i]=v[n][i];

        //每个数的最大值只和它的下一行的数算出的最大值有关。
        for(int i=n-1;i>=1;i--)
            for(int j=1;j<=i;j++)//j只能是从1开始，而不能是从i开始，因为这样数据会被覆盖
                s[j]=v[i][j]+max(s[j],s[j+1]);
        cout<<s[1]<<endl;
    }//end while

    return 0;
}