【动态规划】——数塔(java版,超详图解)

个人主页:个人主页​ 系列专栏:数据结构与算法 数塔问题 [问题描述]从数塔的顶层…

个人主页:个人主页
​ 系列专栏:数据结构与算法

数塔问题

[问题描述]从数塔的顶层出发,在每一个结点可以选择向左走向右走,直走到最底层,要求找出一条路径,使得路径上的数值和最大

问题分析:要求出路径上的数值和最大,只需求出“8"左边(12)和右边(15)的数塔谁最大即可。

  • 左边(12)
  • 要求12这个数塔的路径上的数值和最大,只需求出“12"左边(3)和右边(9)的数塔谁最大
  • 要求3这个数塔的路径上的数值和最大,只需求出“3"左边(8)和右边(10)的数塔谁最大
  • 要求9这个数塔的路径上的数值和最大,只需求出”9"左边(10)和右边(5)的数塔谁最大
  • ………………………………………………..等等等
  • 右边(15)
  • 要求15这个数塔的路径上的数值和最大,只需求出“15"左边(9)和右边(6)的数塔谁最大
  • 要求9这个数塔的路径上的数值和最大,只需求出“9"左边(10)和右边(5)的数塔谁最大
  • 要求6这个数塔的路径上的数值和最大,只需求出”6"左边(5)和右边(12)的数塔谁最大
  • ………………………………………………..等等等
  • 可以看出:动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

我们的解题思路:先求子问题,也就是先求出底层的最大值,例如:先求出第4层各数的路径最大值(这里因为第4层是最底层,也就是它本身),然后第3层通过判断自己下面层数的左边和右边(第4层,例如8下面的 16(左)和4(右))谁更大,从而求出第3层各数路径的最大值,有点抽象,给大家一张图来解释一下:

我们从最底下开始看,因为第4层是最底层,所以最大值为它本身,也就是图中的初始化

分别为16 4 18 10 9。再看第3层,8的左边分别为16和4,因为16最大 故此 以8为根的这个数塔路径最大值为24,同理 以10为根的这个数塔路径最大值为28,以5为根的这个数塔路径最大值为23,以12为根的这个数塔路径最大值为22。以此类推,求出了路径上的数值和最大为60

开始写代码:

首先数塔我们用二维数组存储

分析:

表示这个数下面的两个数和自身相加 取一个最大的。

例如:

以8为例

d[i][j]=Math.max(d[i+1][j]+d[i][j],d[i+1][j+1]+d[i][j]);

d[i][j]=Math.max(16+8,4+8)=24

因为一开始我们是以倒数第二层的 8 先开始的

所以一开始

i=d.leng-2(也就是8的行数位置索引)

j=0(也就是8的列数位置索引)

完整代码:

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/6423.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部