换钱最少货币数

发表于 | 分类于

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

解法一：
时间空间复杂度都为O(N*aim)

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 mincoinsl(int[] arr, int aim){
	if (arr == null || arr.length == 0 || aim < 0){
		return -1;
	}
	int n = arr.length;
	int max = Integer.MAX_VALUE;
	int[][] dp = new int[n][aim+1];
	for (int j = 1; j < aim +1; j ++){
		dp[0][j]  = max;
		if (j - arr[0] >= 0 && dp[0][j-arr[0]] != max){
			dp[0][j] = dp[0][j-arr[0]] + 1;
		}
	}
	
	int left = 0;
	for (int i = 1; i < n; i++){
		for (int j = 1; j < aim +1; j++){
			left = max;
			if (j - arr[i] >=0 && dp[i][j-arr[i]] != max)			{
				left = dp[i][j-arr[i]] +1;
			}
			dp[i][j] = Math.min(left,dp[i-1][j]);		
		}
	}
	
	return dp[n-1][aim] != max ? dp[n-1][aim]:-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
public int mincoinsl(int[] arr, int aim){
	if (arr == null || arr.length== 0|| aim <0){
		return -1;
	}
	int n = arr.length;
	max = Integer.MAX_VALUE;
	int[] dp = new int[aim+1];
	
	for (int j = 1; j < aim+1; j++){
		dp[j] = max;
		if (j-arr[0]>=0 && dp[j-arr[0]] !=max){
			dp[j] = dp[j-arr[0]] + 1;
		}
	}
	
	int left = 0;
	for (int i = 1; i < n; i ++){
		for (int j = 1; j < aim+1; j++){
			if (j- arr[i]>=0&& dp[j-arr[i]] !=max)
				left = dp[j-arr[i]] +1;
			dp[j]= Math.min(left,dp[j]);
		}
	}
	return dp[aim] != max ? dp[aim]:-1;
}