货币金额凑整问题

题目：给定一个数组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;
    }