poj_3176

this time the dp array is a two dimensional array, attaching to the data array

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int **way;
    int ans=0;
    way=new int*[n];
    for(int i=0;i<n;i++){
        //each line,receive input
        way[i] = new int[i+1];//0->0;1->0,1
        for(int j=0;j<=i;j++){
            cin>>way[i][j];
        }
    }
    //dp stars
    ans=way[0][0];
    for(int i=1;i<n;i++){
        //dismiss first level
        for(int j=0;j<=i;j++){//0,1--level two
            if(j>=1&&j<i){//optimazation
                way[i][j]+=max(way[i-1][j-1],way[i-1][j]);
            }
            if(j==0){
                way[i][0]+=way[i-1][0];
            }
            if(j==i){
                way[i][i]+=way[i-1][i-1];
            }
            if(i==n-1){//bottom
                for(int k=0;k<n;k++){
                    if(way[i][k]>ans){
                        ans=way[i][k];
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}