题目

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

递归搜索

首先介绍暴力递归的方法。如果arr=[5,10,25,1]，aim=1000，分析过程如下:

  1. 用0张5元的货币，让[丨0,25，1]组成剩下的1000，最终方法数记为res1。

  2. 用1张5元的货币，让[10,25，1]组成剩下的995，最终方法数记为res2。

  3. 用2张5元的货币，让[10,25，1]组成剩下的990，最终方法数记为res3。

    ……

  4. 用200张5元的货币，让[10,25,1]组成剩下的0，最终方法数记为res201。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

	public static int coins1(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim < 0) {
			return 0;
		}
		return process1(arr, 0, aim);
	}

	public static int process1(int[] arr, int index, int aim) {
		int res = 0;
		if (index == arr.length) {
			res = aim == 0 ? 1 : 0;
		} else {
			for (int i = 0; arr[index] * i <= aim; i++) {
				res += process1(arr, index + 1, aim - arr[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中查询这个递归过程是否己经计算过，如果己经计算过，就把值拿出来直接用，如果没计算过，需要再进入递归过程。它和coinsl方法的区别就是准备好全局变量map,记录已经计算过的递归过程的结果，防止下次重复计算。

因为本题的递归过程可由两个变量表示，所以map是一张二维表。map[i][j]表示递归过程 p(i,j)的返回值。另外有一些特别值，map[i][j]==0表示递归过程p(i,j)从来没有计算过。map[i][j]=-1表示递归过程计算过，但返回值是0。如果map[i][j]的值既不等于0，也不等于-1,记为a,则表示递归过程的返回值为a。

记忆化搜索的方法是针对暴力递归最初级的优化技巧，分析递归函数的状态可以由哪些变量表示，做出相应维度和大小的map即可。记忆化搜索方法的时间复杂度为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

	public static int coins2(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim < 0) {
			return 0;
		}
		int[][] map = new int[arr.length + 1][aim + 1];
		return process2(arr, 0, aim, map);
	}

	public static int process2(int[] arr, int index, int aim, int[][] map) {
		int res = 0;
		if (index == arr.length) {
			res = aim == 0 ? 1 : 0;
		} else {
			int mapValue = 0;
			for (int i = 0; arr[index] * i <= aim; i++) {
				mapValue = map[index + 1][aim - arr[index] * i];
				if (mapValue != 0) {
					res += mapValue == -1 ? 0 : mapValue;
				} else {
					res += process2(arr, index + 1, aim - arr[index] * i, map);
				}
			}
		}
		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][k*arr[0]]=l(0<=k*arr[0]<=aim，k 为非负整数)。

  3. 除第一行和第一列的其他位置，记为位置(i，j)。dp[i][j]的值是以下几个值的累加。

    • 完全不用arr[i]货币，只使用arr[0..i-1]货币时，方法数为dp[i-l][j]。

    • 用1张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-arr[i]]。

    • 用2张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-2*arr[i]]。

    • 用k张arr[i]货币，剩下的钱用arr[0..i-1]货币组成时，方法数为dp[i-1][j-k*arr[i]]。j-k*arr[i]>=0，k为非负整数。

  4. 最终dp[N-1][aim]的值就是最终结果。

步骤3中，第1种情况的方法数为dp[i-1][j],而第2种情况一直到第k种情况的方法数累加值其实就是dp[i][j-arr[i]]的值。所以步骤3可以简化为dp[i][j]=dp[i-1][j]+dp[i][j-arr[i]]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

	public static int coins5(int[] arr, int aim) {
		if (arr == null || arr.length == 0 || aim < 0) {
			return 0;
		}
		int[] dp = new int[aim + 1];
		for (int j = 0; arr[0] * j <= aim; j++) {
			dp[arr[0] * j] = 1;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = 1; j <= aim; j++) {
				dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0;
			}
		}
		return dp[aim];
	}

动态规划与记忆化搜索的区别

在本质上记忆化搜索方法等价于动态规划方法。记忆化搜索的方法说白了就是不关心到达某一个递归过程的路径，只是单纯地对计算过的递归过程进行记录，避免重复的递归过程，而动态规划的方法则是规定好每一个递归过程的计算顺序，依次进行计算，后计算的过程严格依赖前面计算过的过程。两者都是空间换时间的方法，也都有枚举的过程，区别就在于动态规划规定计算顺序,而记忆搜索不用规定。所以记忆化搜索方法的时间复杂度也是O(N*aim^2)

两者各有优缺点，如果对暴力递归过程简单地优化成记忆搜索的方法，递归函数依然在使用，这在工程上的开销较大。而动态规划方法严格规定了计算顺序，可以将递归计算变成顺序计算，这是动态规划方法具有的优势。其实记忆搜索的方法也有优势，本题就很好地体现了。比如，arr=[20000，10000，1000], aim=2000000000。如果是动态规划的计算方法，要严格计算3x2000000000个位置。而对于记忆搜索来说，因为面值最小的钱为1000,所以百位为(1~9)、十位为(1〜9)或各位为(1~9)的钱数是不可能出现的，当然也就不必要计算。通过本例可以知道，记忆化搜索是对必须要计算的递归过程才去计算并记录的。