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  目標錢數(shù)
     * @return  返回值：方法數(shù)
     */
    public static int process1(int[] arr, int index, int aim) {
        int res = 0;
        if (index == arr.length) {//如果index已經(jīng)到了數(shù)組的最后位置，已經(jīng)終止了，
            res = aim == 0 ? 1 : 0;//遞歸過程一直在選擇，有效的標準：沒有余數(shù)，無效的標準：還有余數(shù)
        } 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

如何避免大量的重復(fù)計算：使用一個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);//在返回之前會把計算完的結(jié)果，全部塞到map里去
        return res;
    }

Image 5.png

例子：

Image 6.png

Image 7.png