动态规划入门02

递归转为递推

从最后一行开始向上反推
例如对于：
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;
}