换钱的方法数

发表于 | 分类于

给定数组arr,arr中所有的值都为正数且不重复。每个值代表一种面值的货币，没中面值的货币可以使用人一丈，再给定一个正数aim代表要找的钱数，求换钱有多少种方法。
解法一：暴力递归

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

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

public int process1(int[] arr, index, int aim){
	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;
}

解法二：记忆搜索。使用map记录已经计算过的值，当使用0张5元和1张10元情况和使用2张5元和0张10元的情况是一样的。所以记录index和aim-arr[index]*i值

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
public int cosins1(int[] arr, int aim){
	if(arr == null || arr.length == 0 || aim < 0){
		return -1;
	}
	int[][] map = new int[arr.lenth+1][aim+1];
	return process1(arr,index,aim,map);
}

public int process1(int[] arr, int index, int aim, int[][] map){
	int res = 0;
	if (index == arr.length){
		res = aim ==0 ?1:0;
	}
	else{
		int maxvalue = 0;
		for (int i=0; arr[index] *i<=aim; i++){
			mapvalue = int[index+1][aim-arr[index]*i];
			if (mapvalue !=0){
				res += mavalue ==-1?0:mapvalue;
			}else{
				res += process1(arr,index+1,aim,map);
			}
		}
	}
	map[index][aim] = res == 0? -1:res;
	return res;
}

解法三：

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
public int coins3(int[] arr, int aim){
	if(arr == null || arr.length == 0 || aim < 0){
		return -1;
	}
	
	int[][] dp = new int[arr.length][aim+1];
	for(int i=0; i< arr.length; i++){
		dp[i][0] = 1;
	}
	
	for (int j = 1; arr[0] * j<=aim; j++){
		dp[0][j] = 1;
	}
	
	int num = 0;
	
	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[i][j] = num;
		}
	}
	return dp[arr.length][aim];
}

解法三：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int coins3(int[] arr, int aim){
	if(arr == null || arr.length == 0 || aim < 0){
		return -1;
	}
	
	int[][] dp = new int[arr.length][aim+1];
	for (int i =0; i< arr.length; i++){
		dp[i][0] = 1;
	}
	
	for (int j = 1; j *arr[0] <= aim; j++){
		dp[0][j*arr[0]] = 1;
	}
	
	for (int i = 1; i< arr.length; i++){
		for (int j = 1; j<= aim; j++){
			dp[i][j] = dp[i-1][j];
			dp[i][j] +=j-arr[i] >= 0 ? dp[i][j-arr[i]]:0;
		}
	}
	
}

解法四：动态规划+空间压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int coins3(int[] arr, int aim){
	if(arr == null || arr.length == 0 || aim < 0){
		return -1;
	}
	
	int[] dp = new int[aim+1];
	
	
	for (int j = 1; j *arr[0] <= aim; j++){
		dp[j*arr[0]] = 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;
		}
	}
	
}

通过本题目的优化过程，可以梳理出暴力递归通用的优化过程。一般先想到暴力递归的过程，在通过查看函数中有哪些参数是不发生变化的，忽略不变化的，只看变化的，并且可以表示递归过程的参数，找到这些参数之后，记忆搜索的方法就可以写出来，将计算完成的记录保存到map中，并在下次直接拿来使用。之后看每个位置是通过哪个位置求出来的，先求出被依赖的位置，就能写出动态规划，如果依赖的位置