矩阵最小路径和

题目（算法课第八课）

给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和。

举例

如果给定的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