递归转为递推
从最后一行开始向上反推
例如对于：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
倒数第二行的每一个和，都等于最后一行两条路线中更大的那个，加上自身的值的和——以此类推。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int D[101][101];
int n;
int maxSum[101][101];
int main(){
int i,j;
cin>>n;
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
cin>>D[i][j];
}
}
memcpy(maxSum,D,sizeof(D));
for(i=n-1;i>=1;i--){
for(j=1;j<=i;j++){
maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
}
}
cout<<maxSum[1][1]<<endl;
return 0;
}
存储空间上可以进一步优化：
#include <iostream>
#include <algorithm>
using namespace std;
int D[101][101];
int n;
int main(){
int i,j;
cin>>n;
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
cin>>D[i][j];
}
}
for(i=n-1;i>=1;i--){
for(j=1;j<=i;j++){
D[i][j]=max(D[i+1][j],D[i+1][j+1])+D[i][j];
}
}
cout<<D[1][1]<<endl;
return 0;
}
