题目要求
提示:头歌 算法作业 实验七 动态规划 第1关:数塔问题
本关任务:编写用动态规划解决数塔问题。
一、解题关键要点(头歌题目已经给)
二、解题过程
1.关于数塔问题的动态规划过程自分析【重点】
求解过程(自底向上)
决策结果输出过程(自顶向下)
将上述分析求解过程角标记录为path数组 ,方便顺序输出结果
2.解题代码
代码如下(不知题目给出三维数组的a的第三维我用处,去除):
#include <stdio.h>
#define N 5 //问题规模
int main() {
int a[50][50];
a[1][1] = 9;
a[2][1] = 12, a[2][2] = 15;
a[3][1] = 10, a[3][2] = 6, a[3][3] = 8;
a[4][1] = 2, a[4][2] = 18, a[4][3] = 9, a[4][4] = 5;
a[5][1] = 19, a[5][2] = 7, a[5][3] = 10, a[5][4] = 4, a[5][5] = 16;
int i, j, dp[50][50] = { 0 }, path[50][50] = { 0 };
for (j = 1; j <= N; j++) //初始子问题 ,倒数第二层(第i-1层)开始
dp[N][j] = a[N][j];
for (i = N - 1; i >= 1; i--) //进行第 i+1 层的决策,从i 到 1 向上
for (j = 1; j <= i+1; j++) { //每一层有 i+1 个
if (dp[i + 1][j] > dp[i + 1][j + 1]) {
dp[i][j] = a[i][j] + dp[i + 1][j];
path[i][j] = j; //本次决策选择下标j的元素
}
else {
dp[i][j] = a[i][j] + dp[i + 1][j + 1];
path[i][j] = j + 1; //本次决策选择下标j+1的元素
}
}
printf("max=%d\n", dp[1][1]);
printf("数值和最大的路径是:");
j = path[1][1]; //计算dp[1][1]的选择
for (i = 1; i < N; i++)
{
printf("%d->", a[i][j]);
j = path[i][j]; //计算dp[i][j]的选择
}
printf("%d\n", a[i][j]);
}
3.运行结果
文章来源:https://www.toymoban.com/news/detail-513395.html
总结
上课没好好听这块😶🌫️,到做题了,瞎揣一气,望指正😢文章来源地址https://www.toymoban.com/news/detail-513395.html
到了这里,关于【算法设计与分析】动态规划:数塔问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!