Kotlin程序员如何在二维数组中寻找最短路线

【出自TX面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

寻找一条从左上角（arr[0][0]）到右下角（arr[m-1][n-1]）的路线，使得沿途经过的数组中的整数的和最小。

分析与解答：

对于这道题，可以从右下角开始倒着来分析这个问题：最后一步到达arr[m-1][n-1]只有两条路：通过arr[m-2][n-1]到达或通过arr[m-1][n-2]到达，假设从arr[0][0]到arr[m-2][n-1]沿途数组最小值为f（m-2，n-1），到arr[m-1][n-2]沿途数组最小值为f（m-1，n-2）。因此，最后一步选择的路线为min{f（m-2，n-1），f（m-1，n-2）}。同理，选择到arr[m-2][n-1]或arr[m-1][n-2]的路径可以采用同样的方式来确定。

由此可以推广到一般的情况。假设到arr[i-1][j]与arr[i][j-1]的最短路径的和为f（i-1，j）和f（i，j-1），那么到达arr[i][j]的路径的上所有数字和的最小值为f（i，j）=min{f（i-1，j），f（i，j-1）}+arr[i][j]。

方法一：递归法

根据这个递归公式可知，可以采用递归的方法来实现，递归的结束条件为遍历到arr[0][0]。在求解的过程中还需要考虑另外一种特殊情况：遍历到arr[i][j]（当i=0或j=0）的时候，只能沿着一条固定的路径倒着往回走直到arr[0][0]。根据这个递归公式与递归结束条件可以给出实现代码如下：

程序的运行结果如下：

17(www.xing528.com)

这种方法虽然能得到题目想要的结果，但是效率太低，主要是因为里面有大量的重复计算过程，比如在计算f（i-1，j）与f（j-1，i）的过程中都会计算f（i-1，j-1）。如果把第一次计算得到的f（i-1，j-1）缓存起来就不需要额外的计算了，而这也是典型的动态规划的思路，下面重点介绍动态规划方法。

方法2：动态规划法

动态规划法其实也是一种空间换时间的算法，通过缓存计算中间值，从而减少重复计算的次数，从而提高算法的效率。方法1从arr[m-1][n-1]开始逆向通过递归来求解，而动态规划要求正向求解，以便利用前面计算出来的结果。

对于本题而言，显然，f（i，0）=arr[0][0]+…+arr[i][0]，f[0，j]=arr[0][0]+…+arr[0][j]。根据递推公式：f（i，j）=min{f（i-1，j），f（i，j-1）}+arr[i][j]，从i=1，j=1开始顺序遍历二维数组，可以在遍历的过程中求出所有的f（i，j）的值，同时，把求出的值保存到另外一个二维数组中以供后续使用。当然在遍历的过程中可以确定这个最小值对应的路线，在这种方法中，除了求出最小值以外顺便还打印出了最小值的路线，实现代码如下：

程序的运行结果如下：

路径：[0，1] [0，2] [2，0] [2，1] [2，2]

最小值为：17

算法性能分析：

这种方法对二维数组进行了一次遍历，因此其时间复杂度为O（m*n）。此外由于这种方法同样申请了一个二维数组来保存中间结果，因此其空间复杂度也为O（m*n）。