给你一个二维数组， 二维数组中的每个数都是正数， 要求从左上角走到右下角， 每一步只能向右或者向下。 沿途经过的数字要累加起来。 返回最小的路径和。
解：
暴力递归
* 因为是从左上角到右下角，只能向右或者向下，
* 可以使用递归，
* 把问题简化为
* 当前位置(i, j)和右边位置(i + 1, j)和下面位置(i, j + 1)之间的问题
* base case：
* 当i == row - 1 && j == col - 1时，位于矩阵右下角，即为最终结果
* 当i == row - 1时，位于最后一行，此时只能向右走
* 当j == col - 1时，位于最右一行，此时只能向下走
* 当位于矩阵中间某个位置时(i, j)，
* 此时要判断右边位置(i + 1, j)和下面位置(i, j + 1)中的值谁大谁小
动态规划
* 是从结果倒推回去推初始状态
* 1.dp数组的维度与大小：递归中的可变参数是 i, j 两个，所以dp数组是二维的 dp[matrix.length][matrix[0].length]
* 2.dp中需要位置为 初始位置(0, 0)
* 3.利用base case把不被依赖的位置标出来：
* 右下角位置
* 4.根据下面的递归调用分析普遍位置中的依赖关系：
* 最下面一行(row - 1, j)依赖的位置是(row - 1, j + 1)
* 最右边一列(i, col - 1)依赖的位置是(i + 1, col - 1)
* 当前位置(i, j)依赖的位置有(i + 1, j), (i, j + 1)
暴力递归版本：
//正着递归
public static int minPath1(int[][] matrix){
if(matrix.length <= 0 || matrix[0].length <= 0 || matrix == null) return 0;
return path(matrix, 0, 0);
}
public static int path(int[][] matrix, int i, int j){
if(i == matrix.length - 1 && j == matrix[0].length - 1) return matrix[i][j];
if(i == matrix.length - 1) return matrix[i][j] + path(matrix, i, j + 1);
if(j == matrix[0].length - 1) return matrix[i][j] + path(matrix, i + 1, j);
return matrix[i][j] + Math.min(path(matrix, i + 1, j),
path(matrix, i, j + 1));
}
其实还可以倒着递归
改为动态规划版本：
正着推
不被依赖的位置是(0, 0)，
普通位置的依赖关系：(i, j) 依赖它左边(i, j - 1)和上边(i - 1, j)位置
最终结果是（row - 1, col - 1）
//正着推
public static int dpMinPath1(int[][] matrix){
if(matrix.length == 0 || matrix[0].length == 0 || matrix == null) return 0;
int row = matrix.length;
int col = matrix[0].length;
int[][] dp = new int[row][col];
//不被依赖的位置
dp[0][0] = matrix[0][0];
//最左一列，只能从上面往下面走
for(int i = 1; i < row; i++){
dp[i][0] = dp[i - 1][0] + matrix[i][0];
}
//最上面一行，只能从左边往右边走
for(int i = 1; i < col; i++){
dp[0][i] = dp[0][i - 1] + matrix[0][i];
}
//普通的位置(i, j)，可以从左边到达(i, j - 1)，也可以从上边到达(i - 1, j)
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + matrix[i][j];
}
}
return dp[row - 1][col - 1];
}
还可以倒着推
不被依赖的位置(row - 1, col - 1)
普通位置的依赖关系：(i, j)依赖它右边(i, j + 1)和下边(i + 1, j)的位置
最终结果是(0, 0)位置的值
//倒着推
public static int dpMinPath2(int[][] matrix){
if(matrix.length == 0 || matrix[0].length == 0 || matrix == null) return 0;
int row = matrix.length;
int col = matrix[0].length;
//dp数组，用来记录各个位置的状态
int[][] dp = new int[row][col];
//不被依赖的位置
dp[row - 1][col - 1] = matrix[row - 1][col - 1];
//最右边的一列
for(int i = row - 2; i >= 0; i--){
dp[i][col - 1] = dp[i + 1][col - 1] + matrix[i][col - 1];
System.out.println("dp["+ i +", "+ (col - 1) + "] " + dp[i][col - 1]);
}
System.out.println();
//最下面一行
for(int i = col - 2; i >= 0; i--){
dp[row - 1][i] = dp[row - 1][i + 1] + matrix[row - 1][i];
System.out.println("dp["+ (row - 1) +", "+ i + "] " + dp[row - 1][i]);
}
//普通位置的值
for(int i = row - 2; i >= 0; i--){
for(int j = col - 2; j >= 0; j--){
dp[i][j] = matrix[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
}
}
return dp[0][0];
}
测试代码
生成随机矩阵
public static int[][] generateRandomMatrix(int row, int col){
if(row <= 0 || col <= 0) return null;
int[][] matrix = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
matrix[i][j] = (int) (Math.random()*10);
}
}
return matrix;
}
测试代码：
public static void main(String[] args) {
int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } };
System.out.println(minPath1(m));
System.out.println(dpMinPath1(m));
System.out.println(dpMinPath2(m));
m = generateRandomMatrix(6, 7);
System.out.println(minPath1(m));
System.out.println(dpMinPath1(m));
System.out.println(dpMinPath2(m));
}