Image 2.png
-
暴力递归：
Image 1.png
public static int coins1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
return process1(arr, 0, aim);
}
/**
*
* @param arr 不变的变量
* @param index 可以任意自由使用index及其之后所有的钱
* @param aim 目标钱数
* @return 返回值：方法数
*/
public static int process1(int[] arr, int index, int aim) {
int res = 0;
if (index == arr.length) {//如果index已经到了数组的最后位置，已经终止了，
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;
}
Image 3.png
Image 4.png
如何避免大量的重复计算：使用一个map记录
public static HashMap<String,Integer> map = new HashMap<>();
public static int process_map(int[] arr,int index,int aim) {
int res =0;
if(index ==arr.length) {
res =aim ==0?1:0;
}else {
for(int zhang =0;arr[index]*zhang<=aim;zhang++) {
int nextAim = aim-arr[index]*zhang;
String key = String.valueOf(index+1)+"_"+String.valueOf(nextAim);//先把下一层递归的key生成出来
if(map.containsKey(key)) {//然后看看之前算没有算过
res+=map.get(key);//如果map里面含有了这个key，说明之前算过，就不进行递归了，直接从 map里面拿出来，直接累加
}else {//只有 map里面没有的情况下，才进行递归
res+=process_map(arr,index+1,nextAim);
}
}
}
map.put(String.valueOf(index)+"_"+String.valueOf(aim ), res);//在返回之前会把计算完的结果，全部塞到map里去
return res;
}
Image 5.png
例子：
Image 6.png
Image 7.png
