【lego】第六十四题：最小路径

算法之狐 11-05 508

前言：

目前同学们对“数据结构图的最短路径算法有哪些”都比较看重，小伙伴们都想要知道一些“数据结构图的最短路径算法有哪些”的相关内容。那么小编在网上网罗了一些有关“数据结构图的最短路径算法有哪些””的相关知识，希望你们能喜欢，我们一起来了解一下吧！

大家好，今天来讲 lego 中的难度题！

1. 今天讲第六十四题最小路径和，给定一个包含非负整数的 m 层 n 网格 grade，要找出一条从左上角到右下角的路径，使路径上数字总和最小，且每次只能向下或向右移动一步。

2. 比如给定例子，电脑为 1、3、1，能得到最小的 7，即从初始位置 0 要到达 m-1、n-1 的位置，可以向左、向右或向下，到达中间位置可以是上面下来或左边过来。

3. 这是典型的动态规划，二维动态规划要注意处理边界，如从左边走，经过 3 后总路径和为 4，到下一位置加前面的 4 为 5，左边没有则是 1+1 得 2，4+2 得 6，这是边界情况。

4. 中间除边界外，可以从上面或左边来，取最小值，如例子中到达某位置，上面过来是 2，左边过来是 4，选 2，以此类推。

5. 写代码时，先获取行列数，函数是 lensgrade，列数是 lengthgrade0，然后初始化上边界，行不变列变，从 1 到 n-1，行是 0，列是 i，要把前面的都累加，如 3+1 得 4，1+4 得 5。接着处理左边界，从上下来，行变，从 1 到 m 行，行是 i，列不变是 0。

6. 处理完边界后推中间，从 1 到 n-1，从 1 到 m-1 行，从 1 到 m-n-1 列，像之前说的选上面和左边的最小值，aj 加上自己等于 mean mini read 上一行 i-1，左边一列 i-1。

7. 整个推完后右下角坐标上的值就是最终最小值，即 return grade，成功是负 1。

8. 写完测试，没问题后提交，这道题相对简单，就是二维动态规划，要考虑边界，除边界外取上面或左边最小值，逐个累加，n-1、m-1、n-1 位置就是最小值。

今天的课程讲完了，谢谢大家。

Dijkstra 单源最短路径算法