算法进阶六

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