经典的DP问题，DP思想也很直接：
直接贴代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int max_size=1001; 7 int n, a[max_size][max_size]; 8 int f[3][max_size]; 9 void initiate(){ 10 memset(a,-1,sizeof(a)); 11 memset(f,0,sizeof(f)); 12 for(int i=1;i<=n;i++){ 13 for(int j=1;j<=i;j++){ 14 scanf("%d",&a[i][j]); 15 } 16 } 17 } 18 void solve(){ 19 int pt_row=n; 20 for(int column=1;column<=n;column++){ 21 f[pt_row%2][column]=a[pt_row][column]; 22 } 23 for(int row=n-1;row>=1;row--){ 24 for(int pt_col=1;pt_col<=row;pt_col++){ 25 f[(pt_row-1)%2][pt_col]=a[pt_row-1][pt_col]+max( 26 f[pt_row%2][pt_col], 27 f[pt_row%2][pt_col+1] 28 ); 29 } 30 --pt_row; 31 } 32 printf("%d ",f[pt_row%2][1]); 33 } 34 int main(){ 35 while(scanf("%d",&n)!=EOF){ 36 initiate(); 37 solve(); 38 } 39 return 0; 40 }