动态规划算法求解数塔问题C语言,动态规划 数塔问题求解 C++实现
时间: 2023-07-08 15:06:52 浏览: 79
以下是C语言实现动态规划算法求解数塔问题的代码:
```c
#include <stdio.h>
#define MAX_N 100
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, a[MAX_N][MAX_N], dp[MAX_N][MAX_N];
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
scanf("%d", &a[i][j]);
}
}
for (int j = 1; j <= n; j++) {
dp[n][j] = a[n][j];
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
}
}
printf("%d\n", dp[1][1]);
return 0;
}
```
以下是C++实现动态规划算法求解数塔问题的代码:
```c++
#include <iostream>
#define MAX_N 100
using namespace std;
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n, a[MAX_N][MAX_N], dp[MAX_N][MAX_N];
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}
for (int j = 1; j <= n; j++) {
dp[n][j] = a[n][j];
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
}
}
cout << dp[1][1] << endl;
return 0;
}
```