正文

OptimalSolution(1)--递归和动态规划（2）矩阵的最小路径和与换钱的最少货币数问题

IP云
IP云V管理员/0 阅读
09/14
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

一、矩阵的最小路径和

1 3 5 9 1 4 9 18 1 4 9 18
8 1 3 4 9 9 5 8 12
5 0 6 1 14 14 5 11 12
8 8 4 0 22 22 13 15 12
最小路径和最小的路径为：1 → 3 → 1 → 0 → 6 → 1 → 0

问题描述，给定矩阵m如上面所示，从左上角开始每次只能向右或者向下走，最后到达右下角，求最小路径和。

假设矩阵m的大小为M×N，首先生成大小和m一样的矩阵dp，dp[i][j]的值表示从开始位置(0,0)走到(i.j)位置的最小路径和。

对于dp矩阵的第一行和第一列来说，如果要走到第一行的第3个，那么必定要经过第一行的第2个，也就是说第一行和第一列就是m[0][0...j]和m[0...j][0]这些值累加的结果，因此dp矩阵现在为上图的第2个矩阵。

除了第一行和第一列之外，对于所有的(i,j)，其前一步要么是(i-1,j)要么是(i,j-1)，也就是说要想到达(i,j)，必定经过(i-1,j)或(i,j-1)，为了求最短的路径和，对于除了第一列和第一行之外的点，只需要使得dp[i][j] = min{dp[i][j-1], dp[i-1][j]} + m[i][j]即可，然后dp矩阵变成了上图中的第3个矩阵。

所以，要求得最短路径和，就是dp矩阵的右下角的值，即为12。

1.使用二维数组（时间复杂度O(M×N)，空间复杂度O(M×N)）求矩阵的最小路径和的解法

public int minPathSum1(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) return 0;
int row = m.length, 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];
}

2.使用空间压缩方法利用一维数组（时间复杂度O(M×N)，空间复杂度O(min{M，N})）求矩阵的最小路径和的解法。

这道题可以使用一维数组来对空间复杂度进行优化，也就是不使用M×N的数组，仅仅使用长度为min{M，N}的数组即可。

首先生成长度为4的数组arr，初始化arr={0,0,0,0}，到达第一行的每个位置和dp一致，也就是先设置成arr={1,4,9,18}，此时的arr[j]的值就代表从(0,0)位置到达(0,j)的最小路径和。

然后，如果想把arr[j]更新成从(0,0)到(1,j)的话，也就是arr[0]代表从(0,0)到(1,0)的最短路径和，此时只需要arr[0] = arr[0]+m[1][0]=9即可，而arr[1]代表从(0,0)到(1,1)的最短路径和，此时从(0,0)到(1,1)有两种选择，一种是从(1,0)到(1,1)，一种是从(0,1)到(1,1)，前者可以用arr[1]+m[1][1]表示，而后者则可以用arr[0]+m[1][1]表示，因此arr[1]= min{arr[0],arr[1]} + m[1][1]，同理，arr[2] = min{arr[1],arr[2]}+m[1][2]，第二行更新完成后，arr为{9,5,8,12}，也就是dp矩阵的第二行。

接着，不断重复上面的步骤，让arr数组依次变成dp矩阵的每一行，最后变成了最后一行，取最后一个数即可。

如果给定的M>N，同样可以令数组长度等于N，然后从左往右，令arr数组依次变为dp矩阵的每一列即可，这样就可以保证空间复杂度为O(min{M，N})。

public int minPathSum2(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);
int less = Math.min(m.length, m[0].length);
boolean rowmore = more == m.length; // 如果行数大于列数，rowmore为true
int[] arr = new int[less];
arr[0] = m[0][0];
// 如果行数大于列数，那么arr为dp的第一行，如果行数小于列数，那么arr为dp的第一列
for (int i = 1; i < less; i++) arr[i] = arr[i - 1] + (rowmore ? m[0][i] : m[i][0]);
// 如果行数大，arr已经是第一行，然后每一行遍历;如果列数大，arr已经是第一列，然后没一列遍历
for (int i = 1; i < more; i++) {
// 如果行数大，那么新arr[0]表示原arr[0]向下走一步；如果行数大，那么新arr[0]表示原arr[0]向右走一步
arr[0] = arr[0] + (rowmore ? m[i][0] : m[0][i]);
for (int j = 1; j < less; j++) {
// 如果行数大，那么i表示行,于是[i][j]；如果列数大，那么i表示列，于是[j][i]
arr[j] = Math.min(arr[j - 1], arr[j]) + (rowmore ? m[i][j] : m[j][i]);
}
}
return arr[less - 1];
}

3.总结

压缩空间的方法几乎可以应用到所有需要二维动态规划的题目中，通过一个数组滚动更新的方式无疑节省了大量的空间。没有优化之前，取得某个位置动态规划值的过程是在矩阵中进行两次寻址，优化后，这一过程只需要一次寻址，程序的常数时间也得到了一定程度的加速。但是空间压缩的方法时有局限的，如果题目改成“打印具有最小路径和的路径”，那么就不能使用空间压缩的方法。因为空间压缩的方法是滚动更新的，会覆盖掉之前求解的值，让求解轨迹变得不可回溯。

二、换钱的最少货币数

1.题目：给定数组arr，且arr中所有值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张。给定一个整数aim代表要找的钱数，求组成aim的最小货币，钱不能找开的情况下默认返回-1。例如arr={5,2,3}，如果aim=20，就返回4，因为货币数最少。

（1）经典动态规划方法

如果arr的长度为N，则生成行数为N、列数为aim+1的动态规划表dp。dp[i][j]的含义是：在可以使用任意张arr[i]货币的情况下，组成j所需的最小张数。

步骤1，dp[0...N-1][0]（dp矩阵的第一列）表示要找的钱数为0时，所需要的张数，即完全不需要货币，因此全设为0。

步骤2，dp[0][0...aim]（dp矩阵的第一行）表示只能使用arr[0]货币的情况下，找某个钱的最小张数。例如，假设arr[0]=2，那么dp[0][2]=1,dp[0][4]]=2,dp[0][6]=3...其他位置均找不开，所以设置为Integer.MAX_VALUE

步骤3，剩下的位置依次从左到右，再从上往下计算。假设计算到位置(i,j)，dp[i][j]的值可能来自下面的情况

  • 完全不使用当前货币arr[i]情况下的最小张数：即dp[i-1][j]的值
  • 只使用1张当前货币arr[i]情况下的最小张数：即dp[i-1][j-arr[i]]+1
  • 只使用2张当前货币arr[i]情况下的最小张数：即dp[i-1][j-2*arr[i]]+1
  • 只使用3张当前货币arr[i]情况下的最小张数：即dp[i-1][j-3*arr[i]]+1
  • ...

也就是要求min{dp[i-1][j]，min{dp[i-1][j-arr[i]]+1，dp[i-1][j-2*arr[i]]+2， dp[i-1][j-3*arr[i]]+3 ... dp[i-1][j-x*arr[i]]+x}(x>=1)}

即dp[i][j] =min{dp[i-1][j-q*arr[i]] + q (q>=0)} min{dp[i-1][j], min{dp[i-1][j-x*arr[i]+x(x>=1)}

令x=y+1，则dp[i][j] = min{dp[i-1][j], min{dp[i-1][j-arr[i] - y*arr[i] + y + 1(y>=0)}而这里因为dp[i][j] =min{dp[i-1][j-q*arr[i]] + q (q>=0)} 所以

令j=j-arr[i],得到dp[i][j] = min{dp[i-1][j], min{dp[i-1][j-arr[i] - y*arr[i]] + y + 1(y>=0)}即dp[i][j] = min{dp[i-1][j], dp[i][j-arr[i] + 1}

所以，最终由dp[i][j] = min{dp[i-1][j], dp[i][j-arr[i]+1}，如果j-arr[i]<0，则说明arr[i]太大，用一张arr[i]后都会超过j，此时令dp[i][j]=dp[i-1][j]即可。

经典动态规划算法（时间复杂度和空间复杂度都是O(N×aim)）

（2）

2.题目：给定数组arr，且arr中所有值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用一张。给定一个整数aim代表要找的钱数，求组成aim的最小货币，钱不能找开的情况下默认返回-1。例如arr={5,2,5,3}，如果aim=10，就返回2，因为货币数最少。

三、换钱的最少方法数