动态规划dp;

方法一（超时）： 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxx=500;
int d[maxx][maxx];
int a[maxx][maxx];
int n,m;
int dfs(int x,int y){
	if(d[x][y]==0){
		d[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));
	}
	return d[x][y];
}
int main(){
	while(cin>>n){
		memset(d,0,sizeof(d));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=i;j++){
				cin>>a[i][j];
				if(i==n){
					d[i][j]=a[i][j];
				}
			}
		}
		int maxsum=dfs(1,1);
		cout<<maxsum<<endl;
	}
	return 0;
} 
方法二：（从下往上） 
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxx=390;
int d[maxx][maxx];
int a[maxx][maxx];
int n,m;
int main(){
	while(cin>>n){
		memset(d,0,sizeof(d));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=i;j++){
				cin>>a[i][j];
				if(i==n){
					d[i][j]=a[i][j];
				}
			}
		}
		for(int i=n-1;i>=1;i--){
			for(int j=1;j<=i;j++){
				d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);
			}
		}
		cout<<d[1][1]<<endl;
	}
	return 0;
} 
方法三：（从上往下）
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxx=390;
int d[maxx][maxx];
int a[maxx][maxx];
int n,m;
int main(){
	while(cin>>n){
		memset(d,0,sizeof(d));
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++){
			for(int j=1;j<=i;j++){
				cin>>a[i][j];
			}
		}
		d[1][1]=a[1][1]; 
		for(int i=2;i<=n;i++){
			for(int j=1;j<=i;j++){
				d[i][j]=a[i][j]+max(d[i-1][j],d[i-1][j-1]);
			}
		}
		int maxin=0;
		for(int i=1;i<=n;i++){
			if(maxin<d[n][i]){
				maxin=d[n][i];
			}
		}
		cout<<maxin<<endl;
	}
	return 0;
}