0%

换钱的方法数

发表于 分类于
本文字数： 阅读时长 ≈

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

举例：
arr = [5,10,25,1],aim = 0;方法有1种，即所有面值的货币都不适用，返回1。
arr = [5,10,25,1],aim = 15;方法有6种，3张5元；1张10元、1张5元；1张10元、、5张1元；10张1元、1张5元；2张5元、5张1元；15张1元，所以返回6。

递归方法
递归方法代码如下：
主方法：

1
2
3
4
5
6
7
   public static int coins1(int[] arr,int aim) {
	
	if (arr == null || arr.length == 0 || aim < 0) {
		return 0;
	}
	return process1(arr,0,aim);
}
1
2
3
4
5
6
7
8
9
10
11
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;
	}