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();

    }

}