// Triangle via top down dynamic programming
#include<fstream>
#include<sstream>
#include<iostream>
using namespace std;
const int max_rows=4;
int memo[max_rows][max_rows+1];
void init_memo(){
for(int i=0; i<max_rows; i++)
for(int j=0; j<max_rows+1; j++)
memo[i][j]=-1;
}
int max_value(int t[][max_rows+1], int i, int j){
if(__________________________)
return t[____________][_______________];
if(______________________________)
return memo[i][j];
return memo[i][j]= t[____][____]+max( _______________________________ );
}
int main()
{ init_memo(); // set all entries = -1
ifstream in("http://venus.cs.qc.cuny.edu/~waxman/211/triangle.txt");
string line;
int t[max_rows][max_rows+1]={0};
for(int i=0; i<max_rows;i++){
getline(in,line);
stringstream si(line);
t[i][0]=0;
for(int j=1;j< i+2;j++ )
si>>t[i][j];
}
int result=max_value(t,max_rows-1,1);
for(int i=2; i<=max_rows;i++){
int k=max_value(t,max_rows-1,i);
if(result<max_value(t,max_rows-1,i))
result=max_value(t,max_rows-1,i);
}
cout<<"the result is: "<<result<<endl;
system("PAUSE");
return 0;
}