递归和动态规划——矩阵的最小路径和（经典动态规划问题

Posted on | In ,

题目：给定一个矩阵m,从左上角开始，每次只能向下或向右走一步，最后达到右下角的位置。路径上所有的数字累加起来就是路径和，返回所有的路径和中最小的路径和。
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

分析：

  1. 先生成与m大小一样的矩阵dp，dp[i][j]表示从左上角（即(0,0)位置）走到(i,j)位置的最小路径和。
  2. 对于m的第一行所有位置来说，从(0,0)走到(0,j)只能往右走，路径和就是m[0][0,..j]这些值累加的结果；
    对于m的第一列所有位置来说，从(0,0)走到(j,0)只能往下走，路径和就是m[0,..j][0]这些值的累加结果。
  3. 除第一行和第一列外，所有的位置都有从上走下来的（i-1，j）位置，和从左走来的（i，j-1）位置。所以dp[i][j]=min{dp[i-1][j], dp[i][j-1]} + m[i][j]。
    若矩阵中有M*N个位置，每个位置都是计算一次（0,0）位置到达自己位置的最小路径和，计算时只比较上边的最小位置和左边的最小位置哪个更小，所以时间复杂度为O(M*N)；由于申请了新的矩阵dp，大小为M*N，所以额外空间复杂度为O(M*N)，其中M、N为m的行数和列数。

动态规划进阶：数组滚动更新
这道经典动态规划问题在经过空间压缩后，时间复杂度依然是O(M*N)，但额外空间复杂度可以降到O(min{M, N})。也就是不再使用M*M的dp矩阵，而是使用min{M, N}的arr数组。数组中存的是到[i][j]的路径最小值的和。

  1. 先生成长度为min{M,N}的数组arr，初始状态为arr=[0,0,0,0]（若M、N中的最小值为列4）。有M行，即将数组arr滚动更新M次。
  2. 对于第1行，结果就是m[0][j]的值，即arr=[1, 3, 5, 9]。
  3. 对于第2行，arr[0]=1+8=9，arr[1]=min{arr[0] + arr[1]}+m[i][1]=5….
  4. 直到将5行更新完毕。

优点：一是节省了大量空间。二是没有优化之前，取得某个位置动态规划值的过程时进行两次寻址，即dp[i-1][j]和dp[i][j-1]寻址；而进行优化后，只需要一次寻址，程序的常数时间也得到了一定程度加速。
缺点：由于数组滚动更新，会导致解轨迹不可回溯，因此杜宇需要求解最优解的具体路径，往往需要完整的动态规划表。

注意，m[0][0]始终是个特殊位置，单独赋值；
m[0][j]和m[i][0]也是特殊行和特殊列，也需要单独考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 计算矩阵从左上角到右下角的最小路径和
public class MinPathSum { 
	/**
	 * 额外开辟与m大小一样的新矩阵dp来记录路径最小值
	 * 时间复杂度和额外空间复杂度为O(M*N)，其中M、N为矩阵m行数和列数。
	 * @param m 矩阵
	 * @return 最小路径和
	 */
	public int minPathSum1(int[][] m) {
		//如果矩阵m的行为空，或行数为0，或列为空，或列数为0，返回0
		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第一列赋值
			dp[i][0] = dp[i - 1][0] + m[i][0];
		}
		for (int j = 1; j < col; j++) { //为dp第一行赋值
			dp[0][j] = dp[0][j - 1] + m[0][j];
		}
		//为非0行和非0列赋值
		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]; //返回dp右下角元素值
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
	/**
	 * 数组滚动更新
	 * @param m
	 * @return
	 */
	public int minPathSum2(int[][] m) {
		int row = m.length;
		int col = m[0].length;
		int n1 = Math.min(row, col);
		int n2 = Math.max(row, col);
		int[] arr = new int[n1];
		arr[0] = m[0][0];
		boolean colIsMin = n1 == m[0].length; //如果N=min{M,N}，列数较小
		//对数组arr第一次更新，需要确定arr是m的第一行还是第一列
		for (int i = 1; i < n1; i++) {
			arr[i] = arr[i - 1] + (colIsMin ? m[0][i] : m[i][0]);
		}
		//对m的后面几行或几列更新
		for (int i = 1; i < n2; i++) {
			//第一列或第一行比较特殊，因为它没有左边和上边的m，单独赋值
			arr[0] = arr[0] + (colIsMin ? m[i][0] : m[0][i]); 
			for (int j = 1; j < n1; j++) {
				arr[j] = Math.min(arr[j - 1], arr[j]) + (colIsMin ? m[i][j] : m[j][i]);
			}
		}
		return arr[n1 - 1]; //返回数组arr的最后一个元素
}
1
2
3
4
5
6
7
8
9
10
11
12
13
	//Test
	public static void main(String[] args) {
		int[][] a = {
			{1,3,5,9},
			{8,1,3,4},
			{5,0,6,1},
			{8,8,4,0}
		};
		MinPathSum mps = new MinPathSum();
		System.out.println("利用辅助矩阵得到的最小路径：" + mps.minPathSum1(a));
		System.out.println("利用辅助数组得到的最小路径：" + mps.minPathSum2(a));
	}
}