【正确答案】对于这道题，可以从右下角开始倒着来分析：最后一步到达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]。
   方法1：递归法
   根据这个递归公式可知，可以采用递归的方法来实现，递归的结束条件为遍历到arr[0][0]。在求解的过程中，还需要考虑另外一种特殊情况：遍历到arr[i][j](当i=0或j=0)的时候，只能沿着一条固定的路径倒着往回走直到arr[0][0]。
   但是递归算法效率太低，主要因为里面有大量的重复计算过程，比如在计算(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)的值，同时，把求出的值保存到另外一个二维数组中以供后续使用。当然，在遍历的过程中可以确定这个最小值对应的路线，在这个算法中，除了求出最小值外顺便还打印出了最小值的路线，实现代码如下：
   public class Test
   {
   public static int getMinPath(int[][]arr){
   if(arr==null||arr.length==0)
   return 0;
   int row=arr.length;
   inr col=arr[0].length;
   //用来保存计算的中间值
   int[][]cache=new int[row][col];
   cache[0][0]=arr[0][0];
   for(int i=1;i＜col;i++){
   cache[0][i]=cache[0][i-1]+arr[0][i];
   }
   for(int j=1;j＜row;j++){
   cache[j][0]=cache[j-1][0]+arr[j][0];
   }
   //在遍历二维数组的过程中不断把计算结果保存到cache中
   for(int i=1;i＜row;i++){
   for(int j=1;j＜col;j++){
   //可以确定选择的路线为arr[i][j-1]
   if(cache[i-1][j]>cache[i][j-1]){
   cache[i][j]=cache[i][j-1]+arr[i][j];
   System.out.print("["+i+","+(j-1)+"]  ");
   }
   //可以确定选择的路线为arr[i-1][j]
   else{
   cache[i][j]=cache[i-i][j]+arr[i][j];
   System.out.print("["+(i-1)+","+j+"]");
   }
   }
   }
   System.out.println("["+(row-1)+","+(col-1)+"]");
   return cache[row-1][col-1];
   }
   public static void main(String[]args){
   int[][]arr={{1,4,3},{8,7,5},{2,1,5}};
   System.out.print("路径:");
   System.out.println("最小值为:"+getMinPath(arr));
   }
   }
   程序的运行结果为：
   路径：[0,1][0,2][2,0][2,1][2,2]
   最小值为：17
   这个方法对二维数组进行了一次遍历，因此，其时间复杂度为O(m*n)。此外由于这个算法同样申请了一个二维数组来保存中间结果，因此，其空间复杂度也为O(m*n)。