专栏首页算法channel动态规划|约束条件下的三角最短路径

动态规划|约束条件下的三角最短路径

这篇文章总结了题目如何符合动态规划的特点,进而如何利用动态规划求解三角约束条件下的最短路径。

1

题目

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

一套三角路径是指,第k行的第i个元素,只能与第k+1行的第i个元素或第i+1个元素组合,依次规律,到达三角形的bottom.

2

动态规划的特征

求解第k行到bottom的最短路径时,需要求此行的任意一个节点i加上第k+1行到bottom的最短路径,显然这具备了最优子结构的特征;

同时,在求第k-1行到bottom的最短路径时,需要求解第k行到bottom的最短路径,在求第k行到bottom的最短路径时,需要再次求解第k+1行到bottom的最短路径,因此又具备了重复的子问题特征。

综上,可以用动态规划方法求解。

自top到bottom求解,还是自bottom到top? 简单来讲,top层的最短路径一旦求出,这个问题就求出来了,如果从bottom开始求解,bottom的最大路径就是这层各自节点的值。

所以,选择从bottom到top的动态规划算法。

3

列出转移方程

求解第k行到bottom的最短路径时,需要求此行的任意一个节点i加上第k+1行到bottom的最短路径,显然这具备了最优子结构的特征;

题目的输入数据结构: input[n][n]

创建缓存: minpath[n],初始值为最后一层的节点取值。因为是自bottom到top,因此这样赋初始值是合理的,只有一层的最短路径就是在这些节点中选取。

由第k+1层的最短路径,推出第k层的最短路径,标颜色的部分实际上存储着第k+1层的最短路径:

minpath[i] = min(minpath[i], minpath[i+1]) + triangle[k][i];

赋完值后,实际上得到第k层的第i个节点到bottom的最短路径。

因此,遍历第k层的所有节点,便求出了第k层的所有节点到bottom的最短路径,实际上就是更新minpath数组。

以上,问题的分析,不准确的地方,敬请指正。

本文分享自微信公众号 - 算法channel(alg-channel),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 代码风格指南谷歌版

    非常感谢我们的忠实读者 shendeguize,在后台留言告诉我,已经翻译了《谷歌Python代码风格指南》 ,大家这样相互帮助,感觉真是太好。

    double
  • Google Python代码风格指南

    这是关注我的一位粉丝翻译的Google Python代码风格指南,很全面。可以作为公司的code review 标准,也可以作为自己编写代码的风格指南。希望对你...

    double
  • 20 个Python常用术语

    下面是我最近汇总的20+个Python常用术语,了解术语能让我们加深对Python的理解,同时会表现的更加专业。

    double
  • NetScaler 固件升级到11.1版本后管理员界面无法登陆

    最近做了一次Citrix平台的整体升级,由底层XS、应用层XD、XM、PVS访问层NetScaler,在升级Netscaler由10.5到11.1的过程中,出现...

    SuperDream
  • 深度学习与统计力学(II) :深度学习的表达能力

    一些开创性的结果[19,20]表明,只要隐层神经元数量足够多,只有一个隐含层的浅层网络就可以从一个有限维空间到另一个有限维空间,万能地逼近任何Borel可测函数...

    数据酷客
  • ASP.NET Web API 支持 CORS

    Cross-Origin Resource Sharing (CORS) 是W3C草案拟定的浏览器与服务端如何进行跨域请求的方式,其原理是用自定义HTTP头来让...

    张善友
  • c++STL容器之stack容器

    西西嘛呦
  • 一次django内存异常排查

    Django 作为 Python著名的Web框架,相信很多人都在用,自己工作中也有项目项目在用,而在最近几天的使用中发现,部署Django程序的服务器出现了内存...

    coders
  • SAP CRM,C4C和Hybris的页面技术明细信息查看

    按F2就能看到页面的technical data, 就能找到当前页面是哪一个BSP component实现的:

    Jerry Wang
  • 内含20万“不可描述”图片,这个数据集千万别在办公室打开

    他说,这些数据集可以用来训练图像分类器,使用CNN做出来的分类器,分辨上述的5种图像准确度可以达到91%。

    量子位

扫码关注云+社区

领取腾讯云代金券