数据结构与算法-动态规划-换钱的方法数

换钱的方法数

【题目】
给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值
的货币可以使用任意张，再给定一个整数 aim，代表要找的钱数，求换钱有多少种方法。

【举例】
arr=[5,10,25,1]，aim=0。
组成 0 元的方法有 1 种，就是所有面值的货币都不用。所以返回 1。

arr=[5,10,25,1]，aim=15。
组成 15 元的方法有 6 种，分别为 3 张 5 元、1 张 10 元+1 张 5 元、1 张 10 元+5 张 1 元、10
张 1 元+1 张 5 元、2 张 5 元+5 张 1 元和 15 张 1 元。所以返回 6。
arr=[3,5]，aim=2。
任何方法都无法组成 2 元。所以返回 0。

代码：

public static int coins1(int[] arr, int aim) {

        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        System.out.println(onWay(arr, 0, aim));
        System.out.println(onWay2(arr, 0, aim, new int[arr.length + 1][aim + 1]));
        return onWay3(arr,aim);
    }

    /**
     * 暴力递归
     * @param arr
     * @param i 可变参数，位置下标
     * @param rest 可变参数，剩余金额
     * @return
     */
    public static int onWay(int[] arr, int i,int rest ) {
        if(i== arr.length) {
            return rest==0?1:0;
        }
        int count = 0;
        for(int k =0;k*arr[i]<=rest;k++) {
            count += onWay(arr,i+1,rest-k*arr[i]);
        }

        return count;

    }

    /**
     * 记忆化搜索
     * @param arr
     * @param i 可变参数，位置下标
     * @param rest 可变参数，剩余金额
     * @return
     */
    public static int onWay2(int[] arr, int i,int rest ,int[][] map) {
        if(i== arr.length) {
            return rest==0?1:0;
        }
        int count = 0;
        for(int k =0;k*arr[i]<=rest;k++) {
            if(map[i+1][rest-k*arr[i]] != 0) {
                count += map[i+1][rest-k*arr[i]] == -1?0:map[i+1][rest-k*arr[i]];
            } else {
                count += onWay2(arr,i+1,rest-k*arr[i],map);
            }

        }
        map[i][rest] = count==0?-1:count;
        return count;

    }

    /**
     * 动态规划
     * @param arr
     * @param i 可变参数，位置下标
     * @param aim 可变参数，剩余金额
     * @return
     */
    public static int onWay3(int[] arr, int aim) {
        int[][] dp = new int[arr.length + 1][aim + 1];

        for(int i =0;i<=arr.length;i++) {
            dp[i][0] = 1;
        }

        for(int i =1;i*arr[0] <= aim;i++) {
            dp[0][i*arr[0]] = 1;
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                int nums = 0;
                for(int k =0;j-k*arr[i] >= 0;k++) {
                    nums += dp[i-1][j-k*arr[i]];
                }

                dp[i][j] =nums;

            }

        }
        return  dp[arr.length - 1][aim];

    }