树塔问题动态规划 c

树塔问题是一个通过动态规划解决的问题。动态规划是一种用于解决优化问题的算法方法，它将问题分解为子问题，并使用已解决的子问题的解来构建最终解。在树塔问题中，我们从塔的顶部开始，可以选择向左走或向右走，一直走到底层，目标是找到一条路径，使路径上的数值和最大。

下面是使用C语言实现的树塔问题动态规划解法的代码：

#include <iostream>
using namespace std;

int main() {
int a[50][50], i, j, n;
cin >> n;

// 输入数塔数据
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
cin >> a[i][j];
a[i][j][2] = a[i][j]; // 存放路径数值和
a[i][j] = 0; // 存放路径下一结点位置，0代表向下，1代表向右下。初始化为0
}
}

// 动态规划求解最大路径和
for (i = n - 1; i >= 1; i--) {
for (j = 1; j <= i; j++) {
if (a[i + 1][j] > a[i + 1][j + 1]) {
a[i][j] += a[i + 1][j];
a[i][j] = 0;
} else {
a[i][j] += a[i + 1][j + 1];
a[i][j][3] = 1;
}
}
}

// 输出最大路径和
cout << "MAX=" << a << endl;

// 输出最大路径
j = 1;
for (i = 1; i <= n - 1; i++) {
cout << a[i][j][1] << "->";
j = a[i][j];
}
cout << a[n][j] << endl;

return 0;
}