随笔记录

递归DP-找零钱的方法数

2022-6-12 diaba 笔试题

package com.jiucaiyuan.net.question;

/**
 * 找零钱的方法数
 * 给定一个数组，表示总共有币种的面值，（不重复的正数数组）
 * 再给定一个金额数aim，问题是有多少种钱币的组合，可以正好满足指定金额（某一个金额的钱币张数不限）
 *
 * @Author jiucaiyuan  2022/6/12 14:31
 * @mail services@jiucaiyuan.net
 */

public class ChangeMethod {


    /**
     * @param arr arr都是正数，没有重复值，每个面值代表一个货币，每一种都可以用无限张
     * @param aim 要找零钱数
     * @return 组合找零钱的方法数
     */
    public static int way1(int[] arr, int aim) {
        return process(arr, 0, aim);
    }

    /**
     * 可以自由选择使用arr中index后所有的面值
     * 剩余需要组合的钱币数是rest
     *
     * @param arr
     * @param index
     * @param rest
     * @return
     */
    public static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int count = 0; arr[index] * count <= rest; count++) {
            ways += process(arr, index + 1, rest - arr[index] * count);
        }
        return ways;
    }


    /**
     * 时间复杂度 O(N*aim*aim))
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int way2(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int count = 0; arr[index] * count <= rest; count++) {
                    ways += dp[index + 1][rest - arr[index] * count];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    /**
     * way2基础上做斜率优化，当前可以通过前一个进行计算，没必要做枚举的累计
     * 从way2的得到值的规律中观察得到
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int way3(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                //一个位置总是需要自己下方的格子
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    //一个位置总是需要自己下方的格子外，还需要自己本行-一个面值的格子的值
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

    //for test
    public static int[] generateRandomArray(int length, int max) {
        int[] arr = new int[(int) (Math.random() * length) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max) + 1;
        }
        return arr;
    }

    public static void main(String[] args) {
        int len = 10;
        int max = 10;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(len, max);
            int amount = (int) (Math.random() * 3 * max) + max;
            int ways = way1(arr, amount);
            System.out.println("------------------------------" + i + "--------" + ways);
            System.out.println(print(arr) + "<----->" + amount);

            if (ways != way2(arr, amount) || ways != way3(arr, amount)) {
                System.out.println("goooooooood!");
                break;
            }
        }
    }

    private static String print(int[] arr) {
        StringBuffer sb = new StringBuffer();
        for (int a : arr) {
            if (sb.length() == 0) {
                sb.append("[").append(a);
            } else {
                sb.append(",").append(a);
            }
        }
        sb.append("]");
        return sb.toString();
    }
}