0%

动态归化以及空间压缩

发表于 更新于 分类于
本文字数： 阅读时长 ≈

动态规划类算法题

动态规划相关以及动态规划的空间压缩方法。

1,矩阵的最小路径和

一个矩阵n，从左上角到右下角，路径上所有的数字累加起来就是路径和，返回左右路径和中最小的值。
例如，给定一个矩阵，n[0] = {1,3,5,9},n[1] = {8,1,3,4},n[2] = {5,0,6,1},n[3] = {8,8,4,0},路径1,3,1,0,6,1,0是最小的路径和所以返回12，如下所示。

1
2
3
4
1 3 5 9
8 1 3 4
5 0 6 1 
8 8 4 0

经典动态规划的解法
解答：这是经典的动态规划算法，假设矩阵N大小为m*n，先生成大小和N一样的矩阵dp，dp[i][j]就是表示从左上角(0,0)位置走到(i,j)位置的最小路径和。对N的第一行位置来说，(0,j)(0 <= j < n)，从(0,0)位置走到(0,j)位置只能向右走，所以从(0,0)位置到(0,j)的路径和就是N[0][0…j]这些值得累加结果。同理对于N的每一列来说，即(i,0)(0 <= i < m),从(0,0)位置到(i,0)位置的路径和就是N[0…i][0]相加。

1
2
3
4
1 4 9 18
9
14
22

可以发现除了第一行和第一列的位置外其它所有的位置(i,j)都有左边位置(i,j-1)和上面位置(i-1,j),从(0,0)到(i,j)的路径必经过位置(i,j)和位置(i-1,j)，所以dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + N[i][j]。最终生成的dp矩阵如下：

1
2
3
4
1   4   9   18
9   5   8   12       
14  5   11  12
22  13  15  12

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int minPath (int[][] m) {	
	if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
		return 0;
	}
	int row = m.length;
	int column = m[0].length;
	int[][] dp = new int[row][column];
	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 i=1;i<column;i++) {
		dp[0][i] = dp[0][i-1] + m[0][i];
	}
	for (int i =1;i < row;i++) {
		for (int j = 1;j < column;j++) {
			dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + m[i][j];
		}
	}
	
	return dp[row - 1][column - 1];
}

上面代码的时间复杂度为O(m * n)，dp矩阵的大小为m * n，所以额外空间复杂度为O(m * n)。

动态规划 + 空间压缩的方法
经过空间压缩后的方法时间复杂度仍然是O(m * n)，但是额外空间复杂度会减小至O(min(m,n))，也就是不使用大小为m * n的矩阵，而仅仅使用大小为min(m,n)的数组，具体过程如下：

  • 1，生成长度为min(m,n)(也就是行数和列数较小的那个值，在这个例子为4)的数组arr,初始值为arr=[0,0,0,0]，从(0,0)位置到达m中第一行的每一个位置，最小路径就是从(0,0)位置开始累加的结果，所以依次把arr设置为arr=[1,4,9,18]，此时arr[j]的值代表从(0,0)位置到(0,j)位置的最小路径和。
  • 2，步骤1是代表的是从(0,0)到(0,j)的最小路径和，现在想把arr[j]的值更新从(0,0)到(1,j)位置的最小路径和。可知对于arr[0]来说，令arr[0] = arr[0] + m[1,0] = 9,即从(0,0)到(1,0)的最小路径和。至于(1,1)位置，此时有两种路径，从(1,0)到(1,1)、从(0,1)到(1,1)，arr[1] = min(arr[0],arr[1]) + m[1][1]，更新后arr[1]就成为dp[1][1]的值。同理arr[2] = min(arr[1],arr[2]) + m[1][2]，依次类推，最终arr可以更新成[9,5,8,12]。
  • 3，重复步骤2，一直到arr彻底变成dp矩阵的最后一行，整个过程其实就是不听滚动更新arr数组，让arr依次变成dp矩阵每一行的值，最终变成最后一行的值。
    如果矩阵的列数小于行数(M>N)，依然可以用上面的方法更新成dp矩阵每一行的值。但如果给定的列数大于行数(M<N),那么就生成长度为M的arr，然后更新成dp矩阵的每一列值，从左到右滚动过去。
    代码如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public static int minPath2(int[][] m) {
    	if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
    		return 0;
    	}
    	
    	int more = Math.max(m.length, m[0].length);//行数与列数较大的那个为more
    	int less = Math.min(m.length, m[0].length);//行数与列数较小的那个为less
    	boolean rowmore = more == m.length;//行数是不是大于或等于列数
    	int[] arr  = new int[less];
    	arr[0] = m[0][0];
    	for (int i = 1;i < less;i++) {
    		arr[i] = arr[i - 1] + (rowmore ? m[0][i] : m[i][0]);
    	}
    	for (int i = 1;i < more;i++) {
    		arr[0] = arr[0] + (rowmore ? m[i][0] : m[0][i]);
    		for (int j = 1;j < less;j++) {
    			arr[j] = Math.min(arr[j - 1], arr[j]) +
    					(rowmore ? m[i][j] : m[j][i]);
    		}
    	}
    	
    	return arr[less - 1];
    }