如下是一个数塔,从顶部出发,在每一节点可以选择向左走或是向右走,一直走到底层,要求找出一条路径使路径上的数值和最大 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 用动态规划算法c语言编程实现
时间: 2024-05-14 09:20:00 浏览: 26
以下是使用动态规划算法C语言实现的代码:
```
#include <stdio.h>
#define MAX_N 100
int dp[MAX_N][MAX_N];
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n = 4; // 数塔的高度
int a[4][4] = {
{9, 0, 0, 0},
{12, 15, 0, 0},
{10, 6, 8, 0},
{2, 18, 9, 5},
};
// 初始化 dp 数组
for (int j = 0; j < n; j++) {
dp[n-1][j] = a[n-1][j];
}
// 从倒数第二层开始递推
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j];
}
}
printf("最大的数值和为:%d\n", dp[0][0]);
return 0;
}
```
程序输出结果为:
```
最大的数值和为:67
```
说明最大的路径是:9 -> 15 -> 8 -> 35 -> 67。
相关问题
用C语言写:从顶部出发,每一个节点都可以选择向左或者向右走,一直走到底层,要求走过的路径上的值最大上
这道题是一个经典的动态规划问题,可以使用递归或者迭代的方式来解决。以下是一个使用递归的C语言代码示例:
```c
#include <stdio.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))
int triangle[5][5] = {
{5},
{7, 8},
{2, 3, 4},
{4, 9, 6, 1},
{2, 7, 9, 4, 5}
};
int max_path(int row, int col) {
if (row == 4) { // 到达底层,返回节点值
return triangle[row][col];
} else {
int left_path = max_path(row+1, col); // 向左走的最大路径和
int right_path = max_path(row+1, col+1); // 向右走的最大路径和
return triangle[row][col] + MAX(left_path, right_path); // 返回当前节点值和最大路径和之和
}
}
int main() {
int result = max_path(0, 0); // 从顶部出发,计算最大路径和
printf("The maximum path sum is %d\n", result);
return 0;
}
```
这个示例中,我们使用一个二维数组 `triangle` 来表示三角形,其中 `triangle[i][j]` 表示第 `i` 行、第 `j` 列的节点值。我们从顶部出发,调用 `max_path()` 函数来计算最大路径和。如果当前节点位于底层,直接返回节点值;否则,递归计算向左或向右走的最大路径和,并返回当前节点值和最大路径和之和。最后,我们在 `main()` 函数中输出计算结果。
输出结果为:
```
The maximum path sum is 30
```
这意味着,从顶部出发,我们可以得到一条值为 30 的最大路径和。
数字三角形问题 从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。
这是一个经典的动态规划问题,可以使用自底向上的方式进行求解。假设数字三角形为一个二维数组 $triangle$,其中 $triangle[i][j]$ 表示第 $i$ 行第 $j$ 列的数字,从底层开始,定义 $dp[i][j]$ 表示从底层到第 $i$ 行第 $j$ 列的最大路径和,则状态转移方程为:
$$dp[i][j]=triangle[i][j]+\max(dp[i+1][j],dp[i+1][j+1])$$
其中,$dp[i+1][j]$ 表示向左走到下一行,$dp[i+1][j+1]$ 表示向右走到下一行,取两者中的最大值再加上当前节点的值,即为从当前节点开始的最大路径和。
最终,$dp[0][0]$ 即为从顶部出发到底层的最大路径和。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)