题目

换钱的方法数

给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim代表要找的钱数，求换钱有多少种方法。

arr=[5,10,25,1]，aim=0。
组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。
arr=[5,10,25,1]，aim=15。
组成15元的方法有6种，分别为3张5元，1张10元+1张5元，1张10元+5张1元，10张1元+1张5元，2张5元+5张1元，15张1元。所以返回6。
arr=[3,5]，aim=2。
任何方法都无法组成2元。所以返回0。

思路 & 代码

暴力的递归

如果arr=[5,10,25,1]， aim=1000，分析过程如下

  • 用0张5元的货币，让[10,25,1]去组成剩下的1000，最终方法数记为res1。
  • 用1张5元的货币，让[10,25,1]去组成剩下的995，最终方法数记为res2。
  • 用2张5元的货币，让[10,25,1]去组成剩下的990，最终方法数记为res3。
  • …
  • 用200张5元的货币，让[10,25,1]去组成剩下的0，最终方法数记为res201。

那么res1+res2+…+res201的值就是总共的方法数。
根据如上的分析过程定义递归函数process1(arr,index,aim)，
它的含义是如果用arr[index..N-1]这些面值的钱去组成aim的话，
返回总共的方法数。具体实现如下代码中的coins1方法。

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
public int coins1(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	return f1(arr, 0, aim);
}
// 暴力递归，无优化
public static int f1(int[] a, int index, int aim) {
	// 方法数
	int res = 0;
	if (index == a.length) {
		// index已经到了数组的边界，且目标钱数已经减为0，说明这个方法是有效的
		if (aim == 0) {
			res = 1;
		}
	} else {
		for (int i = 0; a[index] * i <= aim; i++) {
			// 注意后面是index+1
			// 因此每次是先index增加，然后index的个数i增加，增加之后要将aim减少
			res += f1(a, index + 1, aim - a[index] * i);
		}
	}
	return res;
}

记忆搜索的方法

接下来介绍基于暴力递归的初步优化的方法，也就是记忆搜索的方法。暴力递归之所以暴力是因为存在大量的重复计算。

  • 当已经使用0张5元+1张10元的情况下，后续应该求[25,1]组成剩下的990的方法总数。
  • 当已经使用2张5元+0张10元的情况下，后续还是求[25,1]组成剩下的990的方法总数。

两个情况下都需要求process1(arr,2,990)。

类似这样的重复计算在暴力递归的过程中大量发生，所以暴力递归方法的时间复杂度非常高并且
和arr中钱的面值有关，最差情况下为O(aim^N)。
记忆化搜索的优化方式。 process1(arr,index,aim)中arr是始终不变的，变化的只有index和aim，
所以可以用p(index,aim)表示一个递归过程。
重复计算之所以大量发生，是因为每一个递归过程的结果都没记下来，所以下次还要重复的去求。
所以可以事先准备好一个map，每计算完一个递归过程，都将结果记录到map中。

当下次进入同样的递归过程之前，先在map中查询是否这个递归过程已经计算过，

  • 如果已经计算过把值拿出来直接用就可以了
  • 如果没计算过再进入递归过程。

具体请参看如下代码中的coins2方法，
它和coins1方法的区别就是准备好全局变量map，记录已经计算过的递归过程的结果，防止下次重复计算。
因为本题的递归过程可由两个变量表示，所以map是一张二维表。
map[i][j]表示递归过程p(i,j)的返回值。

  • map[i][j]==0表示递归过程p(i,j)从来没有计算过。
  • map[i][j]==-1表示递归过程p(i,j)计算过但返回值是0。
  • map[i][j]的值既不等于0也不等于-1，记为a，则表示递归过程p(i,j)的返回值为a。

记忆化搜索方法的时间复杂度为什么也是O(N*(aim^2))

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
//使用map，减少重复计算
public int coins2(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	//map是存储该方法是否计算过，值为-1表示计算过，且为用此方法返回值为0，map值为0，表示没有计算，
	int[][] map = new int[arr.length + 1][aim + 1];
	return f2(arr, 0, aim, map);
}
public static int f2(int[] a, int index, int aim, int[][] map){
	int res = 0;
	if(index == a.length){
		if(aim == 0){
			return 1;
		}
	}else{
		
		for (int i = 0; a[index] * i <= aim; i++) {
			//因为下面要算这个，所以先看看map中是否存储
			int tmp = map[index+1][aim - a[index] * i];
			if(tmp != 0){
				//tmp！=0表示计算过
				if(tmp != -1){
					//tmp=-1表示返回值为0，所以不用加，
					//tmp！=-1有返回值，且不为0
					res += tmp;
				}
			}else{
				//该值map中还没有算过，因此要计算一下
				res += f2(a, index + 1, aim - a[index] * i,map);
			}
			// 每次算完一个循环，更新map,更新的此过程的map，即map[index][aim]
			map[index][aim] = res == 0 ? -1 : res;
		}
	}
	return res;
}

动态规划方法

组成行数为N，列数为aim+1的矩阵dp，
dp[i][j]的含义是在使用arr[0..i]货币的情况下，组成钱数j有多少种方法。

dp[i][j]的值求法如下：
1，对于矩阵dp第一列的值dp[..][0]，表示组成钱数为0的方法数，很明显是1种，也就是不使用任何货币。所以dp第一列的值统一设置为1。
2，对于矩阵dp第一行的值dp[0][..]，表示只能使用arr[0]这一种货币的情况下，组成钱的方法数，
例如arr[0]==5时，能组成的钱数只有0， 5， 10， 15…。所以令dp[0][karr[0]]=1(0<=karr[0]<=aim， k为非负整数)。
3，除了第一行和第一列的其他位置，记为位置(i,j)。 dp[i][j]的值是以下几个值的累加。
0）完全不用arr[i]货币，只使用arr[0..i-1]货币时，方法数为dp[i-1][j]。
1）用1张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-arr[i]]。
2）用2张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-2*arr[i]]。
…

k）用k张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-karr[i]]。
j-karr[i]>=0， k为非负整数。
4，最终dp[N-1][aim]的值就是最终结果。
具体过程请参看如下代码中的coins3方法。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public static int coins3(int[] arr, int aim) {
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	//dp[i][j]表示使用arr[0..i]货币的情况下，组成钱数j有多少种方法
	int[][] dp = new int[arr.length][aim + 1];
	//初始化
	for (int i = 0; i < arr.length; i++) {
		//使用arr[0..i]货币的情况下，组成钱数0有1种
		dp[i][0] = 1;
	}
	for (int j = 1; arr[0] * j <= aim; j++) {
		////使用arr[0]货币的情况下，只能组成arr[0]的倍数的钱数
		dp[0][arr[0] * j] = 1;
	}
	
	int num = 0;
	//dp[i][j]使用dp[i-1][j]即不使用arr[i]的货币，组成j的方法数
	//当使用arr[i]的货币的时候
	//那么使用1张arr[i]，有dp[i-1][j-arr[i]]
	//那么使用2张arr[i]，有dp[i-1][j-arr[i]*2]
	//...因此当使用k张arr[i]的货币，方法数为dp[i-1][j-arr[i]*k]
	for (int i = 1; i < arr.length; i++) {
		for (int j = 1; j <= aim; j++) {
			num = 0;
			for (int k = 0; j - arr[i] * k >= 0; k++) {
				num += dp[i - 1][j - arr[i] * k];
			}
			//更新dp
			dp[i][j] = num;
		}
	}
	return dp[arr.length - 1][aim];
}
``` 
在最差情况下对于位置(i,j)来说，求解dp[i][j]的计算过程需要枚举dp[i-1][0..j]上的所有值，
dp一共有N*aim个位置，所以总体的时间复杂度为O(N*(aim^2))。
解释之前记忆化搜索方法的时间复杂度为什么也是O(N*(aim^2))，
因为在本质上记忆化搜索方法等价于动态规划方法。
记忆化搜索的方法说白了就是不关心到达某一个递归过程的路径，只是单纯的对计算过的递归过程进行记录，避免重复的递归过程
动态规划的方法则是规定好每一个递归过程的计算顺序，依次进行计算，后计算的过程严格依赖前者计算过的过程。
两者都是空间换时间的方法，也都有枚举的过程，
区别就在于动态规划规定计算顺序而记忆搜索不用规定。
所以记忆化搜索方法的时间复杂度也是O(N*(aim^2))。
两者各有优缺点，
如果对暴力递归过程简单地优化成记忆搜索的方法，递归函数依然在使用，这在过程上的开销较大。
动态规划方法严格规定了计算顺序，可以将递归计算变成顺序计算，这是动态规划方法很大的优势。
其实记忆搜索的方法也有优势，本题就很好的体现了。
例如arr=[20000,10000,1000]， aim=2000000000。
如果是动态规划的计算方法，要严格计算3*2000000000个位置。
对于记忆搜索来说，因为面值最小的钱为1000，所以百位为(1~9)或⼗位为(1~9)或各位为(1~9)的钱数是不可能出现的，当然也就不必要计算。
通过本例可以知道，记忆化搜索是对必须要计算的递归过程才去计算并记录的。
### 优化dp
时间复杂度为O(N*aim)的动态规划方法。
我们来看上一个动态规划方法中，求dp[i][j]值的时候的步骤3，这也是最关键的枚举过程：
3，除了第一行和第一列的其他位置，记为位置(i,j)。 dp[i][j]的值是以下几个值的累加。
0）完全不用arr[i]货币，只使用arr[0..i-1]货币时，方法数为dp[i-1][j]。
1）用1张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-arr[i]]。
2）用2张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-2*arr[i]]。
...
k）用k张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-k*arr[i]]。
j-k*arr[i]>=0， k为非负整数。
步骤3中，情况0）的方法数为dp[i-1][j]，
情况1）一直到情况k）的方法数累加值其实就是dp[i][j-arr[i]]的值。
![推导过程](http://7xilc8.com1.z0.glb.clouddn.com/7.2_dp.png "推导过程")
所以步骤3可以化简为dp[i][j]=dp[i-1][j]+dp[i][j-arr[i]]。
一下省去了枚举的过程，时间复杂度也减为O(N*aim)，具体请参看如下代码中的coins4方法。

//优化dp
public static int coins4(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
// dp[i][j]表示使用arr[0..i]货币的情况下，组成钱数j有多少种方法
int[][] dp = new int[arr.length][aim + 1];
// 初始化
for (int i = 0; i < arr.length; i++) {
// 使用arr[0..i]货币的情况下，组成钱数0有1种
dp[i][0] = 1;
}
for (int j = 1; arr[0] j <= aim; j++) {
// 使用arr[0]货币的情况下，只能组成arr[0]的倍数的钱数
dp[0][arr[0] j] = 1;
}
//计算其余的dp
for (int i = 1; i < arr.length; i++) {
for (int j = 1; j <= aim; j++) {
//dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]]
//先要判断j-arr[i]是否越界
dp[i][j] = dp[i-1][j];
if(j-arr[i] >= 0){
dp[i][j] += dp[i-1][j-arr[i]];
}
}
}
return dp[arr.length - 1][aim];
}
```