随笔记录

递归DP-金币组合最少金币数

2022-6-5 diaba 笔试题

package com.jiucaiyuan.net.question;

/**
 * @Author jiucaiyuan  2022/6/5 11:33
 * @mail services@jiucaiyuan.net
 */

public class CoinAmount {
    /**
     * 暴力递归
     * 给一个正数数组，每个数表示一枚硬币的面值，给定一个数值，从硬币中选择得到这个金额的最少硬币数
     * 比如指定硬币有[1,4,7,2,4,3,5,1,3]
     * 指定金额10，那么最少硬币数是7+3，两枚硬币，返回2
     *
     * @param arr    硬币，arr.length硬币个数，arr[index]表示index硬币金额
     * @param amount 组合最终的金额
     * @return 组合最终金额的最少硬币数
     */
    public static int minCoinsCountV1(int[] arr, int amount) {
        return processV1(arr, 0, amount);
    }

    public static int processV1(int[] arr, int index, int rest) {
        //超额了
        if (rest < 0) {
            return -1;
        }
        //金额正好
        if (rest == 0) {
            return 0;
        }
        //钱还有，但是硬币没了
        if (index == arr.length) {
            return -1;
        }
        //钱还有，硬币也还有
        //当前硬币不选择，往后尝试
        int p1 = processV1(arr, index + 1, rest);
        //当前硬币选择，往后尝试
        int p2Next = processV1(arr, index + 1, rest - arr[index]);
        //如果后续尝试后，发现金额超了，不能组成目标金额
        if (p1 == -1 && p2Next == -1) {
            return -1;
        }
        //如果
        if (p1 == -1) {
            return p2Next + 1;
        }
        if (p2Next == -1) {
            return p1;
        }
        return Math.min(p1, p2Next + 1);
    }

    /**
     * 暴力递归添加缓存，去掉重复计算，空间换时间
     * <p>
     * 给一个正数数组，每个数表示一枚硬币的面值，给定一个数值，从硬币中选择得到这个金额的最少硬币数
     * 比如指定硬币有[1,4,7,2,4,3,5,1,3]
     * 指定金额10，那么最少硬币数是7+3，两枚硬币，返回2
     *
     * @param arr    硬币，arr.length硬币个数，arr[index]表示index硬币金额
     * @param amount 组合最终的金额
     * @return 组合最终金额的最少硬币数
     */
    public static int minCoinsCountV2(int[] arr, int amount) {
        int[][] dp = new int[arr.length + 1][amount + 1];
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = -2;//-2表示没有计算过  -1表示计算过，无效
            }
        }
        return processV2(arr, 0, amount, dp);
    }

    ;

    public static int processV2(int[] arr, int index, int rest, int[][] dp) {
        //超额了
        if (rest < 0) {
            return -1;
        }
        if (dp[index][rest] != -2) {
            return dp[index][rest];
        }

        if (rest == 0) {
            //金额正好
            dp[index][rest] = 0;
        } else if (index == arr.length) {
            //钱还有(amount > 0)
            // 没硬币了
            dp[index][rest] = -1;
        } else {
            //硬币也还有
            //当前硬币不选择，往后尝试
            int p1 = processV2(arr, index + 1, rest, dp);
            //当前硬币选择，往后尝试
            int p2Next = processV2(arr, index + 1, rest - arr[index], dp);
            //如果后续尝试后，发现金额超了，不能组成目标金额
            if (p1 == -1 && p2Next == -1) {
                dp[index][rest] = -1;
            } else if (p1 == -1) {
                dp[index][rest] = p2Next + 1;
            } else if (p2Next == -1) {
                dp[index][rest] = p1;
            } else {
                dp[index][rest] = Math.min(p1, p2Next + 1);
            }
        }

        return dp[index][rest];
    }

    /**
     * 动态规划版本
     * <p>
     * 给一个正数数组，每个数表示一枚硬币的面值，给定一个数值，从硬币中选择得到这个金额的最少硬币数
     * 比如指定硬币有[1,4,7,2,4,3,5,1,3]
     * 指定金额10，那么最少硬币数是7+3，两枚硬币，返回2
     *
     * @param arr    硬币，arr.length硬币个数，arr[index]表示index硬币金额
     * @param amount 组合最终的金额
     * @return 组合最终金额的最少硬币数
     */
    public static int minCoinsCountV3(int[] arr, int amount) {
        int[][] dp = new int[arr.length + 1][amount + 1];

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

        for (int col = 1; col <= amount; col++) {
            dp[arr.length][col] = -1;
        }

        for (int index = arr.length - 1; index >= 0; index--) {
            for (int rest = 1; rest <= amount; rest++) {

                //过程改自递归调用的process方法
                int p1 = dp[index + 1][rest];
                int p2Next = rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : -1;

                if (p1 == -1 && p2Next == -1) {
                    dp[index][rest] = -1;
                } else if (p1 == -1) {
                    dp[index][rest] = p2Next + 1;
                } else if (p2Next == -1) {
                    dp[index][rest] = p1;
                } else {
                    dp[index][rest] = Math.min(p1, p2Next + 1);
                }
            }
        }
        return dp[0][amount];
    }


    //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[] array = {4, 9, 10, 4};
        minCoinsCountV2(array, 17);

        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;
            System.out.println("------------------------------" + i);
            System.out.println(print(arr) + "<----->" + amount);
            int minCoinsCountV1 = minCoinsCountV1(arr, amount);
            int minCoinsCountV2 = minCoinsCountV2(arr, amount);
            int minCoinsCountV3 = minCoinsCountV3(arr, amount);
            System.out.println(minCoinsCountV1 + "<----->" + minCoinsCountV2 + "<----->" + minCoinsCountV3);

            if (minCoinsCountV1 != minCoinsCountV2 || minCoinsCountV1 != minCoinsCountV3) {
                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();
    }
}