首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

动态规划经典题目-找零钱的最少硬币数

  • 25-03-07 18:21
  • 4445
  • 10998
blog.csdn.net

文章目录

  • 一、题目描述
  • 二、解题思路(朴素版本)
    • 1. 定义状态
    • 2. 定义状态转移方程
    • 3. 初始化
  • 三、代码实现
  • 四、优化
  • 五、执行结果

一、题目描述

​ 美国的硬币按照面值1, 5, 10, 25, 50来铸造(单位为美分)。现在考虑按照面值{d1,…, dk}(单位为分)来铸造硬币的某个国家。我们想要寻找一个算法能用最少数目的该国硬币来找开n分钱。给出一种高效算法能确定出用面值集合{d1,…, dk}找开n分钱所需的最少硬币数。

​ ———题目来源:《算法设计指南》

示例:

输入:coins = [2,3,5] total = 12
输出:3
解释:2 + 5 + 5最少需要3枚硬币找开12分钱
  • 1
  • 2
  • 3

二、解题思路(朴素版本)

​ 其实本题就是完全背包问题。

1. 定义状态

​ 设dp[i][j]表示使用前i个面值不同的硬币找出零钱j的所用的最少硬币数。

2. 定义状态转移方程

d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j − k × d i ] + k ) dp[i][j] = min(dp[i - 1][j - k \times d_i] + k) dp[i][j]=min(dp[i−1][j−k×di​]+k) ,其中 0 ≤ k ≤ ⌊ j d i ⌋ 0 \leq k \leq \lfloor \frac{j}{d_i} \rfloor 0≤k≤⌊di​j​⌋ 。这里解释一下 d p [ i − 1 ] dp[i-1] dp[i−1]表示使用前 i − 1 i-1 i−1个面值不同的硬币,其中第 i i i个硬币可能使用0个或多个,上限为 ⌊ j d i ⌋ \lfloor \frac{j}{d_i} \rfloor ⌊di​j​⌋ 个,下限为0个。

3. 初始化

​ dp[0][j]表示不使用硬币找出j的最小零钱数,初始化为 Integer.MAX_VALUE - total,注意这里不能初始化为Integer.MAX_VALUE,因为后面用到这个值计算会溢出变为最小值导致程序运行结果不正确。

​ dp[i][0]表示使用前i个面值不同硬币找出0美分所需硬币数,很显然dp[i][0]初始化为0即可。

三、代码实现

/**
 * 第六题 找零钱需要最少的硬币数
 *
 * @author hh
 */
public class Solution {

    /**
     * 求找零钱最小硬币数
     *
     * @param coins 硬币面值集合
     * @param total 找零钱总数
     * @return 最少硬币数
     */
    public int minCoins(int[] coins, int total) {
        int[][] dp = new int[coins.length + 1][total + 1];
        //初始化行
        for (int i = 1; i <= total; i++) {
            //注意下这里的值不能初始化为Integer.MAX_VALUE
            dp[0][i] = Integer.MAX_VALUE - total;
        }
        //初始化列
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= total; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k <= j / coins[i - 1]; k++) {
                    dp[i][j] = Math.min(dp[i][j],dp[i - 1][j - k * coins[i - 1]] + k );
                }
            }
        }
        return dp[coins.length][total];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{2, 3, 5};
        int total = 12;
        Solution solution = new Solution();
        System.out.println(solution.minCoins(coins, total));
    }
}
  • 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

四、优化

对于解题思路中的k其实是没必要计算的,这样就减少了一个循环。状态方程变为:

​ d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − d i ] + 1 ) dp[i][j] = min(dp[i - 1][j],dp[i][j - d_i] + 1) dp[i][j]=min(dp[i−1][j],dp[i][j−di​]+1)

第一个式子表示的含义是不使用第i种硬币凑成零钱j的硬币数。第二个式子表示最少有一枚硬币i凑成零钱总数j的硬币数。

代码如下所示:

public class Solution2 {

    /**
     * 求找零钱最小硬币数
     *
     * @param coins 硬币面值集合
     * @param total 找零钱总数
     * @return 最少硬币数
     */
    public int minCoins(int[] coins, int total) {
        int[][] dp = new int[coins.length + 1][total + 1];
        //初始化行
        for (int i = 1; i <= total; i++) {
            //注意下这里的值不能初始化为Integer.MAX_VALUE
            dp[0][i] = Integer.MAX_VALUE - total;
        }
        //初始化列
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= total; j++) {
                if(j < coins[i-1]){
                    dp[i][j] = dp[i-1][j];
                } else{
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j - coins[i-1]] + 1);
                }
            }
        }
        return dp[coins.length][total];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{2, 3, 5};
        int total = 12;
        Solution2 solution = new Solution2();
        System.out.println(solution.minCoins(coins, total));
    }
}
  • 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

上面是对时间复杂度进行优化,下面对空间进行优化,考虑到dp[i][j]只跟dp[i-1]和dp[i]有关,我们可以把二维降成一维,代码如下所示:

public class Solution3 {

    /**
     * 求找零钱最小硬币数
     *
     * @param coins 硬币面值集合
     * @param total 找零钱总数
     * @return 最少硬币数
     */
    public int minCoins(int[] coins, int total) {
        int[] dp = new int[total + 1];
        //注意下这里的值不能初始化为Integer.MAX_VALUE,因为相加会出现整数溢出
        Arrays.fill(dp,Integer.MAX_VALUE - total);
        dp[0] = 0;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = coins[i-1]; j <= total; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[total];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{2, 3, 5};
        int total = 12;
        Solution3 solution = new Solution3();
        System.out.println(solution.minCoins(coins, total));
    }
}
  • 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

五、执行结果

在这里插入图片描述

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览64430 人正在系统学习中
注:本文转载自blog.csdn.net的仁者乐山智者乐水的文章"https://blog.csdn.net/qq_39559641/article/details/117172758"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top