实现思路

由于网格大小是不确定的，网格上的数字也是不确定的。我们可以知道的是要整条路径的值最小，而又有多条路径，那么就需要知道每一步的最小路径是什么，也就是每一步的数字和为最小。

另外还有两条比较特殊的行和列。

第一行，除了第一个格子，往右移动，每个格子都是由前一个格子决定的。

第一列，除了第一个格子，往下移动，每个格子都是由上一个格子决定的。

而其他的格子都是由左边的格子或者上面的格子决定的。

也就是说，我们知道了第一行和第一列每个格子的路径值，那么其他的格子都可以由此推导出来。

举个例子，题目中给出的示例1。

第一行第一列的值为1。

第一行第二列的值为3，那么此时如果往右走到第一行第二列，路径的数字和就是4。

第二行第一列的值为1，那么此时如果往下走到第二行第一列，路径的数字和就是2。

此时我们可以走第二行第二列，那么我们是从第一行第二列还是从第二行第一列走呢？它们两个各自的路径和已经知道了，我们选取一个最小的留下，路径和最小的为第二行第一列，值为2。

不管网格有多少行多少列，我们只需要根据上面这种方式就可以推导出最后的最短路径。

完整代码

第813行代码，获取整个数组的长度，即总列数。

第814行代码，获取第二维数组的长度，即总行数。

第815-817行代码，如果数组为空则退出。

第819行代码，遍历列数。

第820行代码，遍历行数。

即在列数不变的情况，一次遍历每一行上的数字和。

第821-823行代码，如果列数和行数都为0的话，也就是第一行第一列，则中断此次循环，因为第一行第一列的没有前置路径，所以不需要计算。

第824-827行代码，如果列数为0时，也就是第一列，上面说思路时讲过，第一列上路径的数字和只来自于该格子的上面，所以只需要第一列上一行格子上的数字相加即可。

第828-831行代码，同列数，如果行数为0时，也就是第一行，上面说思路时讲过，第一行上路径的数字和只来自于该格子的左面，所以只需要第一行左一列格子上的数字相加即可。

第832行代码，不属于第一行或者第一列的格子，则需要判断该格子左边或者上边的路径数字和哪一个值最小，然后把最小值赋值给该格子。

第836行代码，返回最后一个格子的路径和，即为整个路径的最小值。因为执行for循环，最后会把$i、$j的值增加到不小于行数或列数，所以需要各自减一得出结果。

本文转载自: 掘金