题目描述：寻找一条从左上角arr[0][0]到右下角arr[m-1][n-1]的路线，使得沿途经过的数组中的整数之和最小 代码：
java版实现：
public class FindRoute { public static int getMinPath(int[][] arr){ if (arr == null || arr.length == 0){ return 0; } int row = arr.length; int 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]; } System.out.println("["+(0)+","+0+"]: " + arr[0][0]); // 在遍历二维数组的过程中不断把计算结果保存到cache中 for (int i = 1; i < row; i++){ for (int j = 1; j < col; j++){ if (cache[i - 1][j] > cache[i][j - 1]){ // 可以确定选择的路线为arr[i][j - 1] cache[i][j] = cache[i][j - 1] + arr[i][j]; System.out.println("["+i+","+(j - 1)+"]: " + arr[i][j - 1]); }else { // 可以确定选择的路线为arr[i - 1][j] cache[i][j] = cache[i - 1][j] + arr[i][j]; System.out.println("["+(i - 1)+","+j+"]: " + arr[i - 1][j]); } } } System.out.println("[" +(row - 1) + "," + (col - 1) + "]" + arr[row - 1][col - 1]); return cache[row - 1][col - 1]; } public static void main(String[] args){ int[][] arr = { {1,4,3,3}, {8,7,5,5}, {2,1,5,5}, {2,1,5,5} }; System.out.println("路径："); System.out.println("最小值为："+getMinPath(arr)); } }