题目:给定一个数组arr,arr中所有的值为正数且不重复,每个值代表一种面值的货币,每种面值的货币可以使用任意张。再刚给定一个整数aim表示要找的钱数,求换钱有多少种方法?
比如:arr = [5, 10, 25, 1]; aim = 1000;
暴力搜索法:
0张5元,10,25,1组成1000,方法数为res1;
1张5元,10,25,1组成995,方法数为res2;
2张5元,10,25,1组成990,方法数为res3;
:                                                        :
:                                                     :
200张5元,10,25,1组成0,方法数为res201;
用剩下的三种货币组成一个钱数,这样的一个过程为一个递归过程,方法的总数为所有res的相加。
定义递归函数,int p1(arr, index, aim),它的含义是如果用arr[index...N-1],这些钱组成aim,返回的方法总数。
暴力搜索存在大量重复,如已经使用0张5元,1张十元情况下,后续将求p1(arr, 2, 990),2表示arr剩下的钱数为arr[2, 3],即【25, 1】;990表示要找的剩余钱数。这种情况与已使用2张5元,0张10元的情况相同,表达式也是p1(arr, 2, 990)。
代码如下:
public int coins1(int[] arr, int aim){
        if (arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        return process1(arr, 0, aim);
    }

    public 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;
    }