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

2019-09-13 admin

动态规划练习题汇总

问题描述:

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 时间复杂度

[转载]原文链接:https://segmentfault.com/a/1190000020379411

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-75060.html

文章标题:动态规划练习题-数字三角形

相关文章
jquery实现动态改变div宽度和高度
完整代码: &lt;!DOCTYPE html PUBLIC &quot;-&#x2F;&#x2F;W3C&#x2F;&#x2F;DTD XHTML 1.0 Transitional&#x2F;&#x2F;EN&quot; &quot;ht...
2017-03-23
Bootstrap jquery.twbsPagination.js动态页码分页实例代码
Bootstrap风格的分页控件自适应的: 参考网址:分页参考文档 1.风格样式: 2.首先引入js文件jQuery.twbsPagination.js &lt;span style=&quot;font-size:14px;&quot;...
2017-03-16
JavaScript使用Max函数返回两个数字中较大数的方法
本文实例讲述了JavaScript使用Max函数返回两个数字中较大数的方法。分享给大家供大家参考。具体如下: JavaScript的Math对象带有一个max函数用于获取两个数字的较大数,下面的代码详细演示了max的用法 &lt;!DOCT...
2017-03-22
JavaScript动态添加style节点的方法
本文实例讲述了JavaScript动态添加style节点的方法。分享给大家供大家参考。具体如下: var css = &#x27;h1 { background: red; }&#x27;, head = document.getEleme...
2017-03-24
JS使用ajax从xml文件动态获取数据显示的方法
本文实例讲述了JS使用ajax从xml文件动态获取数据显示的方法。分享给大家供大家参考。具体分析如下: 下面的JS代码通过ajax检索xml文件的内容动态展示到网页,真个页面无刷新 &lt;!DOCTYPE html&gt; &lt;htm...
2017-03-21
javascript动态创建链接的方法
本文实例讲述了javascript动态创建链接的方法。分享给大家供大家参考。具体分析如下: 动态创建链接示例: &lt;html xmlns=&quot;http:&#x2F;&#x2F;www.w3.org&#x2F;1999&#x2F;...
2017-03-23
javascript实现动态导入js与css等静态资源文件的方法
本文实例讲述了javascript实现动态导入js与css等静态资源文件的方法。分享给大家供大家参考。具体实现方法如下: &#x2F;** * 动态导入静态资源文件js&#x2F;css *&#x2F; var $import = fu...
2017-03-27
javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法
本文实例讲述了javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法。分享给大家供大家参考。具体实现方法如下: &lt;!DOCTYPE html PUBLIC &quot;-&#x2F;&#x2F;W3C&#x2F;...
2017-03-23
JavaScript将数字转换成大写中文的方法
本文实例讲述了JavaScript将数字转换成大写中文的方法。分享给大家供大家参考。具体实现方法如下: function intToChinese ( str ) { str = str+&#x27;&#x27;; var len = ...
2017-03-21
vue 解决addRoutes动态添加路由后,刷新失效问题
你是电,你是光,你是最美的太阳🌞 前言 某些场景下我们需要利用addRoutes动态添加路由,但是刷新后就会失效,前段时间项目里刚好遇到了这个应用场景,所以就花时间研究了一下,做下分享跟记录,说的不对的地方,请大家指正。 **应用场...
2018-06-30
回到顶部