动态规划练习题-数字三角形

2019-09-13

动态规划练习题汇总

问题描述:

clipboard.png

在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。 路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。 三角形的行数大于1小于等于100,数字为 0 - 99

输入:三角形序列:[[7],[3,8],[8,1,0],[2,7,4,4],[4,5,2,6,5]]

输出:最大和,走过的数字序列

1 思路 把三角形看做一个二叉树,根节点为第一层,往第i+1层走时,是在第i层的基础上增加i+1个可选项,用到达第i层的路径和加上可选项,将有最大和的可选项纳入路径

2 拆分子问题 第i层的每个节点都有其最大路径和,往第i+1层走时,每个节点都有两个选项,因此可以计算得到第i+1层每个节点的最大路径和

3 计算 以w(i)(k)表示第i层的第k个节点的值,以S(i+1)作为到达第i+1层的最大路径和,以Sk(i+1)作为第i+1层第k个节点的最大路径和,其中1<=k<=i+1,S(i+1)=max{ Sk(i) + max{w(i+1)(k),w(i+1)(k+1)}, 其中1<=k<=i}

4 代码

5 时间复杂度

原文链接:segmentfault.com

上一篇:如何在Vue Router中应用中间件
下一篇:ueditor图片上传方式处理
相关教程
关注微信

扫码加入 JavaScript 社区

相关文章

首次访问,需要验证
微信扫码,关注即可
(仅需验证一次)

欢迎加入 JavaScript 社区

号内回复关键字:

回到顶部