数塔问题

正向求解，迭代实现

    for(int i = n-1;i >= 1;i --){
        for(int j = 1;j <= i;j ++){
            if(a[i+1][j] > a[i+1][j+1]) a[i][j]+=a[i+1][j];
            else a[i][j]+=a[i+1][j+1];
        }
    }

备忘录，递归实现

输出数塔问题得最优解和最优解值

#include<iostream>

using namespace std;
const int N=110;
int a[N][N],dp[N][N];
int path[N][N];         // 使用二维数组标记最优解的路径
int n,cnt;
int dfs(int u,int v){
    // 备忘录求解
    if(dp[u][v]) return dp[u][v];
    int val1 = dfs(u+1,v),val2 = dfs(u+1,v+1);
    if(val1 > val2) {
        path[u][v] = 0;
        dp[u][v] = a[u][v] + val1;
    }
    else{
        path[u][v] = 1;
        dp[u][v] = a[u][v] + val2;
    }
    return dp[u][v];
}
void display(int k,int i,int j){
    if(k == 1) {
        cout << a[i][j];
        return;
    }
    if(path[i][j] == 1) display(k-1,i+1,j+1);
    else display(k-1,i+1,j);
    cout<<" -> " << a[i][j];
}
int main(){
    int x;
    cin >> x;
    while(n*(n+1)/2 < x) n ++;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= i;j ++){
            scanf("%d",&a[i][j]);
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    // 初始化状态数组
    for(int i=1;i<=n;i++) dp[n][i]=a[n][i];
    dfs(1,1);
    // 最优解值
    cout<<dp[1][1]<<endl;
    cout<<cnt<<endl;
    // 最优解
    display(n,1,1);
    return 0;
}

测试数据

15
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5