题目（算法课第八课）
给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。
举例
如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
思路
思路1：递归
每个位置只能向右 或者 向下走，每次走最短的，无后效性。
代码1：
public static int minPath1(int[][] matrix) {
return minPath1(matrix, 0, 0);
}
public static int minPath1(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 && j != matrix[0].length - 1) {
return matrix[i][j] + minPath1(matrix, i, j + 1);
}
if (j == matrix[0].length - 1 && i != matrix.length - 1) {
return matrix[i][j] + minPath1(matrix, i + 1, j);
}
int right = minPath1(matrix, i, j + 1);
int down = minPath1(matrix, i + 1, j);
return matrix[i][j] + Math.min(right, down);
}
思路2：动态规划
运用动态规划，我们在递归的时候了解到，（i,j）位置的值依赖它左边或者上边的值，所以我们就先把它依赖的求出来，然后从左上开始向（i,j）求，相当于把递归的过程反过来。申请一个新的二维数组空间，分别求出第一行和第一列的累计和的值，然后再求（i,j）位置的值时就可以根据已经求出的第一行和第一列的累计和来算（把每个i,j位置的路径和都算出来），先找出不被依赖的，再求出依赖的。
步骤
假设矩阵m的大小为M×N，行数为M，列数为N。
1. dp[i][j]
生成大小和m一样的矩阵dp，dp[i][j]的值表示从左上角（即(0，0)）位置走到(i ，j)位置的最小路径和。
2. base case
对m的第一行的所有位置来说，即(0，j)(0≤j<N)，从(0，0)位置走到(0，j)位置只能向右走，
所以(0，0)位置到(0，j)位置的路径和就是m[0][0..j]这些值的累加结果。
同理，对m的第一列的所有位置来说，即(i，0)(0≤i<M)，从(0，0)位置走到(i，0)位置只能向下走，
所以(0，0)位置到(i，0)位置的路径和就是m[0..i][0]这些值的累加结果。
以题目中的例子
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
来说，dp第一行和第一列的值如下：
1 4 9 1 8
9
14
22
3. “补表”
除第一行和第一列，其他位置(i ，j)都有左边位置(i-1，j)和上边位置(i ，j-1)。从(0，0)到(i ，j)的路径必然经过位置(i-1，j)或位置(i ，j-1)——所以
dp[i][j]=min{ dp[i-1][j]，dp[i][j-1] }+m[i][j]
含义是比较从(0，0)位置开始，经过(i-1，j)位置最终到达(i，j)的最小路径和经过(i ，j-1)位置最终到达(i ，j)的最小路径之间，哪条路径的路径和更小。
更小的路径和就是dp[i][j]的值。
以题目的例子
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
来说，最终生成的dp矩阵如下：
1 4 9 18
9 5 8 12
14 5 11 12
22 13 15 12
代码2：
public static int minPath2(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length;
int col = m[0].length;
int[][] dp = new int[row][col];
dp[0][0] = m[0][0];
for (int i = 1; i < row; i++) {//第一行计算最短路径,只能向右走
dp[i][0] = dp[i - 1][0] + m[i][0];
}
for (int j = 1; j < col; j++) {//第一列计算最短路径,只能向下走
dp[0][j] = dp[0][j - 1] + m[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
}
}
return dp[row - 1][col - 1];
}
总的代码
public class MinPath {
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(minPath2(m));
}
public static int minPath1(int[][] matrix) {
return minPath1(matrix, matrix.length - 1, matrix[0].length - 1);
}
public static int minPath1(int[][] matrix, int i, int j) {
int res = matrix[i][j];
if (i == 0 && j == 0) {
return res;
}
if (i == 0 && j != 0) {
return res + minPath1(matrix, i, j - 1);
}
if (i != 0 && j == 0) {
return res + minPath1(matrix, i - 1, j);
}
return res + Math.min(minPath1(matrix, i, j - 1), minPath1(matrix, i - 1, j));
}
public static int minPath2(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length;
int col = m[0].length;
int[][] dp = new int[row][col];
dp[0][0] = m[0][0];
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + m[i][0];
}
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + m[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
}
}
return dp[row - 1][col - 1];
}
}
输出：
12
12
网友评论