我是靠谱客的博主 激情御姐,最近开发中收集的这篇文章主要介绍动态规划算法求解数塔问题C语言,动态规划之数塔问题,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题意:

下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大.

算法实现:

I. 首先利用一个二维数组data存储数塔的原始数据,然后利用一个中间数组dp存储每一次决策过程中的结果。

II. 初始化dp,将data的最后一层拷贝到dp中。dp[n][j] = data[n][j] (j = 1, 2, …, n) 其中,n为数塔的层数。

III. 在动态规划过程汇总,我们有dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j],最后的结果保存在dp[0][0]中。

对于上面的数塔,我们的data数组如下:

9

12

15

10

6

8

2

18

9

5

19

7

10

4

16

而我们的dp数组如下:

59

50

49

38

34

29

21

28

19

21

19

7

10

4

16

代码:

#include

#include

using namespace std;

typedef long long LL;

int dp[105][105];

int main()

{

int T;

scanf("%d",&T);

for(int cas=1;cas<=T;++cas){

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++){

for(int j=1;j<=i;j++){

scanf("%d",&dp[i][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]);

}

}

printf("%dn",dp[1][1]);

}

return 0;

}

最后

以上就是激情御姐为你收集整理的动态规划算法求解数塔问题C语言,动态规划之数塔问题的全部内容,希望文章能够帮你解决动态规划算法求解数塔问题C语言,动态规划之数塔问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(65)

评论列表共有 0 条评论

立即
投稿
返回
顶部