• 【算法】【递归与动态规划模块】换钱的最小硬币数

    目录

    前言

    当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

    在此感谢左大神让我对算法有了新的感悟认识！

    问题介绍

    原问题
    有三种面值的硬币{5,3,2}，每一种硬币都有无限个，求组成20元所需最少硬币数量，如果组成不了则返回-1即可
    进阶问题
    原问题基础上，每一种硬币只有一个，求组成20元所需最少硬币数量。

    解决方案

    原问题：
    方法一：暴力递归
    1、遍历每一种硬币，作如下计算：
    当前种硬币使用一个，剩下的交给除了当前硬币所在数组之后的硬币1
    方法二：动态规划
    第一要素：dp[i][j]代表 使用arr[0…i]这几个面值，组成j所需要的最小硬币数
    第二要素：dp[i][j] = min(dp[i-1][j-k*arr[i]] + k]) 其中 k 属于 [0, j/arr[i]]
    方法三：动态规划降低空间维度版本
    基于方法二，需要一个全新的数组作为缓存，保存当前轮的结果，作为下一轮的依据，具体看代码

    代码编写

    java语言版本

    原问题：
    递归方法：

         /**
     * 方法一：暴力递归
     * @param arr
     * @param aim
     * @return
     */
    public static int minCoinCP1(int[] arr, int aim) {
        if (aim < 0 || arr == null || arr.length == 0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }
    // 递归主体
    private static int process1(int[] arr, int start, int aim) {
        if (aim == 0) {
            return 0;
        }
        if (start >= arr.length) {
            return Integer.MAX_VALUE;
        }
        int min = Integer.MAX_VALUE;
        for (int j = 0; j <= aim/arr[start]; j++) {
            int res = process1(arr, start + 1, aim - (j * arr[start]));
            if (res != Integer.MAX_VALUE){
                // 说明凑的齐
                min = Math.min(min, j + res);
            }

        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    标准动态规划：

        /**
     * 方法二：动态规划
     * @param arr
     * @param aim
     * @return
     */
    public static int minCoinCP2(int[] arr, int aim) {
        if (aim < 0 || arr == null || arr.length == 0) {
            return 0;
        }
        int[][] dp = new int[arr.length][aim+1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= aim; i++) {
            dp[0][i] = i%arr[0] == 0 ? i/arr[0] : -1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= j/arr[i]; k++) {
                    // k代表几个arr[i]
                    if (j-k*arr[i] > 0 && dp[i-1][j-k*arr[i]] != -1) {
                        min = Math.min(min, k + dp[i-1][j-k*arr[i]]);
                    }
                }
                dp[i][j] = min == Integer.MAX_VALUE ? -1 : min;
            }
        }
        return dp[arr.length-1][aim];
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    动态规划（节省空间版本）:

        /**
     * 方法三：动态规划空间压缩法
     * @param arr
     * @param aim
     * @return
     */
    public static int minCoinCP3ReduceMem(int[] arr, int aim) {
        if (aim < 0 || arr == null || arr.length == 0) {
            return 0;
        }
        // 上波的结果是否存在dp中
        boolean isFirst = true;
        int[] dp = new int[aim+1];
//        辅助
        int[] dp2 = new int[aim + 1];
        // 初始化
        for (int i = 0; i <= aim; i++) {
            dp[i] = i % arr[0] == 0 ? i / arr[0] : -1;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= j/arr[i]; k++) {
                    if (isFirst) {
                        if (dp[j - k * arr[i]] != -1) {
                            min = Math.min(min, k + dp[j - k * arr[i]]);
                        }
                    }else {
                        if (dp2[j - k * arr[i]] != -1) {
                            min = Math.min(min, k + dp2[j - k * arr[i]]);
                        }
                    }
                }
                if (isFirst) {
                    dp2[j] = min == Integer.MAX_VALUE ? -1 : min;
//                    isFirst = !isFirst;
                }else {
                    dp[j] = min == Integer.MAX_VALUE ? -1 : min;
//                    isFirst = !isFirst;
                }
            }
            isFirst = !isFirst;
        }
        if (isFirst) {
            return dp2[aim] == -1 ? -1 : dp2[aim];
        }else {
            return dp[aim] == -1 ? -1 : dp[aim];
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    进阶问题：
    递归方法（略）
    经典动态规划：

       /**
     * 进阶问题：动态规划
     * @param arr
     * @param aim
     * @return
     */
    public static int minCoinCP2Only(int[] arr, int aim) {
        if (aim < 0 || arr == null || arr.length == 0) {
            return 0;
        }
        int[][] dp = new int[arr.length][aim+1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= aim; i++) {
            dp[0][i] = arr[0] == i ? 1 : -1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= 1; k++) {
                    // k只能是0和1个
                    if (j-k*arr[i] > 0 && dp[i-1][j-k*arr[i]] != -1) {
                        min = Math.min(min, k + dp[i-1][j-k*arr[i]]);
                    }
                }
                dp[i][j] = min == Integer.MAX_VALUE ? -1 : min;
            }
        }
        return dp[arr.length-1][aim];
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    空间压缩动态规划方法：

        /**
     * 方法三：动态规划空间压缩法
     * @param arr
     * @param aim
     * @return
     */
    public static int minCoinCPOnlyReduceMem(int[] arr, int aim) {
        if (aim < 0 || arr == null || arr.length == 0) {
            return 0;
        }
        // 上波的结果是否存在dp中
        boolean isFirst = true;
        int[] dp = new int[aim+1];
//        辅助
        int[] dp2 = new int[aim + 1];
        // 初始化
        for (int i = 0; i <= aim; i++) {
            dp[i] = i == arr[0] ? 1 : -1;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= 1; k++) {
                    if (isFirst) {
                        if (j - k * arr[i] >= 0 && dp[j - k * arr[i]] != -1) {
                            min = Math.min(min, k + dp[j - k * arr[i]]);
                        }
                    }else {
                        if (j - k * arr[i] >= 0 &&dp2[j - k * arr[i]] != -1) {
                            min = Math.min(min, k + dp2[j - k * arr[i]]);
                        }
                    }
                }
                if (isFirst) {
                    dp2[j] = min == Integer.MAX_VALUE ? -1 : min;
//                    isFirst = !isFirst;
                }else {
                    dp[j] = min == Integer.MAX_VALUE ? -1 : min;
//                    isFirst = !isFirst;
                }
            }
            isFirst = !isFirst;
        }
        if (isFirst) {
            return dp2[aim] == -1 ? -1 : dp2[aim];
        }else {
            return dp[aim] == -1 ? -1 : dp[aim];
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    c语言版本

    正在学习中

    c++语言版本

    正在学习中

    思考感悟

    1、这道题其实跟标准的动态规划区别比较大，我第二遍做的时候还是没有想好dp[i][j]应该怎么表示，所以由此悟了一下：
    首先我发现递归的方式是非常容易写出来的，按照之前的思路，总的来说比较简单，但是动态规划的dp[i][j]是其中一个重要的要素，直接想的话并不好想。但是递归好想，那么递归和动态规划的转换应该是一个需要感悟的点，这里我发现递归中每一次传给下一个状态的参数有三个，arr，start，aim，其中arr是常量，start和aim为变量，那么我们可以将状态之间的关系找到，这里关联一下我的另一篇文章，斐波那契数列，f(start, aim) = min( f(start-1, aim - k*aim[start])),
    因为dp的就是递归结果的缓存，那么dp的坐标一定能够唯一确定当前值，也就是决定递归结果的参数变量，所以这里的dp的坐标应该就是两个变量，即start和aim，实际上也确实是的。那么这里我们可能会问一下，三个参数、四个参数时怎么办？dp是否能够多维呢？我认为是可以的，但是有个条件就是递归的几个变量参数之间不能存在关联关系，也就是说start的变化不会引起aim的变化，不能存在一个参数为aim，另一个参数为aim+1，必须是独立的变量才可以。多维的dp目前还没有遇到过，但是一定很有意思~

    写在最后

    方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
    如果需要git源码可邮件给2260755767@qq.com
    再次感谢左大神对我算法的指点迷津！

    1. 这里只讲剩下的数值交给arr[i]之后的硬币是因为前面的硬币已经计算过从0个开始的过程了 ↩︎

  • 相关阅读:
    docker的再定义镜像和上传阿里云
    vue app开发调用原生方法实现权限访问授权处理（一）
    实时渲染路径追踪概述
    梳理拯救烂怂代码？我是这么做的
    Tair的使用
    nginx常用的日志配置
    小波神经网络短期负荷分析,小波神经网络的缺点
    Word文件的只读模式没有密码怎么退出？
    我的NVIDIA开发者之旅-Jetson Nano 2gb教你怎么训练模型（完整的模型训练套路）
    day20--Java集合03
  • 原文地址：https://blog.csdn.net/qq_39760347/article/details/127460219