python用动态规划求最短路径_动态规划之最短路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

昨天做了道算法题，感觉画图很有助于自己理解算法的过程，这次再挑一个算法加深印象。碰到这种类型的题目，和递归很像，但是使用递归，如果数据范围比较大，就会花费很长时间。

动态规划(英语：Dynamic programming，简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

废话少说

解题

根据题意，到达网格中的某个点最短，可以理解为网格中的任何一个点都是可以走过去的，而且任何一个网格都有一个最短的路径。

那么我们使用一种数据结构保存，从顶点到达网格中任意一点的最短位置。根据人的正常逻辑，画图如下：

从顶点按照行来遍历每一个位置，计算每一个位置的最小路径

image-20190320161330569

根据上面的图片可以了解：

当点处于第一行的时候，它的最短路径就是同一行的前一个位置加上当前位置</