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

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

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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jack-Cui

Caffe学习笔记(四):使用pycaffe生成train.prototxt、test.prototxt文件

Python版本: Python2.7 运行平台: Ubuntu14.04 一、前言     了解到上一篇笔记的内容,就可以尝试自己编写python程序生...

1.3K60
来自专栏人工智能LeadAI

深度学习框架之一:Theano | Lasagne简单教程

参考Lasagne官网(http://lasagne.readthedocs.io/en/latest/)tutorial进行总结而来。 01 简介 Lasag...

55950
来自专栏程序生活

Leetcode-Easy 887. Projection Area of 3D Shapes

当时自己没有想到好办法,就是按部就班的分别求三个面的面积,注意求xy的面积的时候需要考虑grid[i][j]值是否为0

11020
来自专栏me的随笔

JavaScript 随机数

JavaScript内置函数random(seed)可以产生[0,1)之间的随机数,若想要生成其它范围的随机数该如何做呢?

16460
来自专栏我的python

如何用pytorch打印出隐藏层梯度

我们在训练神经网络时, 有时会发现自己的网络学习不到东西,loss不下降或者下降很慢,这时除了检查修改学习率以外还有可能是碰见了梯度消失的问题。检...

3.3K40
来自专栏null的专栏

简单易学的机器学习算法——Rosenblatt感知机

一、感知机的概念 image.png 二、感知机模型的训练     1、目标函数    image.png     2、感知机的训练过程 image.png 三...

41390
来自专栏北京马哥教育

python实现拼写检查器21行轻松搞定

引入 大家在使用谷歌或者百度搜索时,输入搜索内容时,谷歌总是能提供非常好的拼写检查,比如你输入 speling,谷歌会马上返回 spelling。 下面是用...

39740
来自专栏数据结构与算法

P1032 字串变换

题目描述 已知有两个字串 A, B 及一组字串变换的规则(至多6个规则):      A1 -> B1      A2 -> B2 规则的含义为:在 A$中的子...

35360
来自专栏锦小年的博客

MNIST数据集的格式转换

以前直接用的是sklearn或者TensorFlow提供的mnist数据集,已经转换为矩阵形式的数据格式。但是sklearn体用的数据集合并不全,一共只有300...

57150
来自专栏码云1024

编程英语之KNN算法

17540

扫码关注云+社区

领取腾讯云代金券