递归和动态规划——换钱最少的货币数（面值可以重复，一张最多使用一次）

Posted on | In ,

题目：给定数组arr,arr中的值可以重复，其中每个值代表一张货币，因此不能重复使用。给定一个数aim，求组成aim的最少货币数。
例：
arr=[5,2,3]，aim=0，不用任何货币就能组成0元，返回0。
arr=[5,2,3]，aim=20,由于不能重复使用，5+2+3<20，不能组成，返回-1。
arr=[5,2,5,3]，aim=10，2张5元的可以组成10元，且张数最少，返回2。

实现：生成M*（aim+1)的矩阵dp，dp[i][j]的含义是，在任意使用arr[0,..i]货币的情况下（每个值仅代表一张货币），组成钱数j的最少货币数。

  1. 对于dp的第一列，即dp[0, M-1][0]，表示需要组成的钱数为0时，需要的最少货币数，由于不需要任何货币就可以组成0，所以dp[0,…M-1][0]=0
  2. 对于dp的第一行，即dp[0][1,…aim]，表示只能只用货币arr[0]的情况下，组成钱数j的最少货币数，只有当j=arr[0]的地方，才找得开（注意一张货币只能使用一次）。其它找不开的地方一律用Integer.MAX_VALUE（2^31-1=2147483647）。
  3. 对于非第一行第一列，dp[i][j]可能来自以下两种情况。
    1）任意使用arr[0,..i]货币包括任意使用arr[0,..i-1]货币，所以dp[i][j]可能等于dp[i-1][j]。
    2）由于arr[i]只有一张不能重复使用，考虑dp[i-1][j-arr[i]](返回到上次未使用arr[i]的地方，即第[i-1]行），这个值代表可以任意使用arr[0,..i-1]情况下，组成钱数j-arr[i]所需的最小张数。从钱数为j-arr[i]到钱数为j，只需要加上当前货币arr[i]。所以dp[i][j]可能等于dp[i-1][j-arr[i]]+1。
    最终得到：
    dp[i][j]=min{dp[i-1][j],dp[i-1][j-arr[i]]+1}
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
32
33
34
35
36
37
38
/**
 * arr中的值可以重复，其中每个值代表一张货币，因此不能重复使用。
 * @param arr 数组中每个值代表一张货币
 * @param aim 需要组成的货币数
 * @return 组成aim的最小货币数
 */
public int minCoins3(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return -1; //不存在用-1表示
	}
	int m = arr.length;
	int n = aim + 1;
	int max = Integer.MAX_VALUE;
	int[][] dp = new int[m][n];
	for (int i = 0; i < m; i++) {
		dp[i][0] = 0;
	}
	for (int j = 1; j < n; j++) {
		dp[0][j] = max;
		if (arr[0] == j) { //只有在j=arr[0]的地方，dp[0][j]使用1张arr[0]
			dp[0][j] = 1;
		}
	}
	//也可以将赋1的部分单独拿出，因为只有这一项为1
	//if (arr[0] < aim) {
	//        dp[0][arr[0]) = 1;
	//}	
	//对于非第一行第一列
	for (int  i = 1; i < m; i++) { 
		for (int j = 1; j < n; j++) { //对于某一行
			int left = max;
			if (j >= arr[i] && dp[i-1][j-arr[i]] != max) {
				left = dp[i-1][j-arr[i]] + 1;
			}
			dp[i][j] = Math.min(left, dp[i-1][j]);
		}
	}
	return dp[m-1][n-1] != max ? dp[m-1][n-1] : -1;
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
	//对上面的函数进行空间压缩优化 O(aim)
	public int minCoins4(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim < 0) {
			 return -1;
		}
		int m = arr.length;
		int n = aim + 1;
		int max = Integer.MAX_VALUE;
		int[] dp = new int[n];
		for ( int j = 1; j < n; j++) {
			dp[j] = max;
			if (arr[0] == j) {
				dp[j] = 1;
			}
		}
		for (int i = 1; i < m; i++) {
			//对于数组dp的某一轮更新
			int left = max; //左上角某个位置的值
			for (int j = n-1; j > 0; j--) {
				if (j >= arr[i] && dp[j - arr[i]] != max) {
					left = dp[j - arr[i]] + 1;
				}
				dp[j] = Math.min(left, dp[j]);
			}	
		}
		return dp[n-1] != max ? dp[n-1] : -1;
	}
}