【正确答案】对于这道题，可以从右下角开始倒着来分析这个问题：最后一步到达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]。根据这个递归公式与递归结束条件可以给出实现代码如下：
   def getMinPath(arr,i,j):
   #倒着走到了第一个结点, 递归结束
   if i==0 and j==0:
   return arr[i][j]
   #选取两条可能路径上的最小值
   elif i＞0 and j＞0:
   return arr[i][j]+\
   min(getMinPath(arr,i-1,j), getMinPath(arr,i,j-1))
   #下面两个条件只可选择一个
   elif i＞0 and j==0:
   return arr[i][j]+getMinPath(arr,i-1,j)
   #j＞0 &&i==0
   else:
   return arr[i][j]+getMinPath(arr, i,j-1)
   
   def getMinPath2(arr):
   if arr==None or len(arr)==0:
   return 0
   return getMinPath(arr, len(arr)-1,len(arr[0])-1)
   
   if __name__=="__main__":
   arr=[[1,4,3],[8,7,5],[2,1,5]]
   print getMinPath2(arr)
   程序的运行结果为：
   17
   这种方法虽然能得到题目想要的结果，但是效率太低，主要是因为里面有大量的重复计算过程，比如在计算f(i-1,j)与f(j-1，i)的过程中都会计算f(i-1,j-1)。如果把第一次计算得到的f(i-1,j-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)的值，同时把求出的值保存到另外一个二维数组中以供后续使用。当然在遍历的过程中可以确定这个最小值对应的路线，在这种方法中，除了求出最小值以外顺便还打印出了最小值的路线，实现代码如下：
   def getMinPath(arr):
   if arr==None or len(arr)==0:
   return 0
   row=len(arr)
   col=len(arr[0])
   #用来保存计算的中间值
   cache=[([None]*col) for i in range(row)]
   cache[0][0]=arr[0][0]
   i=1
   while i＜col:
   cache[0][i]=cache[0] [i-1]+arr[0][i]
   i+=1
   j=1
   while j＜row:
   cache[j][0]=cache[j-1][0]+arr[j][0]
   j+=1
   #在遍历二维数组的过程中不断把计算结果保存到cache中
   print "路径:",
   i=1
   while i＜row:
   j=1
   while j＜col:
   #可以确定选择的路线为arr[i][j-1]
   if cache[i-1][j]＞cache[i][j-1]:
   cache[i][j]=cache[i][j-1]+arr[i][j]
   print "["+str(i)+","+str(j-1)+"] ",
   #可以确定选择的路线为arr[i-1][j]
   else:
   cache[i][j]=cache[i-1][j]+arr[i][j]
   print "["+str(i-1)+","+str(j)+"]",
   j+=1
   i+=1
   print("["+str(row-1)+","+str(col-1)+"]")
   return "最小值为:"+str(cache[row-1][col-1])
   
   if __name__=="__main__":
   arr=[[1,4,3],[8,7,5],[2,1,5]]
   print getMinPath(arr)
   程序的运行结果为：
   路径：[0,1] [0,2][2,0] [2,1] [2,2]
   最小值为：17
   算法性能分析：
   这种方法对二维数组进行了一次遍历，因此其时间复杂度为O(m*n)。此外由于这种方法同样申请了一个二维数组来保存中间结果，因此其空间复杂度也为O(m*n)。

【答案解析】[考点] 如何在二维数组中寻找最短路线