遞歸轉(zhuǎn)為遞推
從最后一行開始向上反推
例如對于：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
倒數(shù)第二行的每一個和，都等于最后一行兩條路線中更大的那個镊屎，加上自身的值的和——以此類推邻梆。
代碼
#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;
}
存儲空間上可以進一步優(yōu)化：
#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;
}
