动态规划——零钱兑换问题

这篇具有很好参考价值的文章主要介绍了动态规划——零钱兑换问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

零钱兑换问题 I

1、题目:力扣原题

动态规划——零钱兑换问题

2、分析

(1)结合我们之前分析的(动态规划解决背包问题),这里硬币有无限个对应完全背包问题。但又存在一点区别:纯完全背包是能否凑成总的金额,本题是要求凑成总金额的组合个数

(2)要注意是求解组合 还是排列 问题。例如 221 和121可以表示一种组合或者两种排列。组合之间不强调元素之间的顺序,而排列强调元素之间的顺序。

DP五部曲分析如下:

1)确定dp含义

        dp[j]: 表示凑成总金额j可以得到的货币组合总数;

2)确定递推公式‘’

        dp[j] (考虑coins[i]的组合总和) 就是所有的dp[j - coins[i]](不考虑coins[i])相加。

        所以递推公式:dp[j] += dp[j - coins[i]];

求装满背包有几种方法,一般公式都是:dp[j] += dp[j - nums[i]];

3)初始化

        dp[0]=1,表示凑成金额为0的货币组合数为1;

4)确定遍历顺序

        这里就要根据上面讨论的来进行区别,题目是要求组合数还是排列数需要对遍历顺序进行处理。因为纯完全背包求得是能否凑成总和,和凑成总和的元素有没有顺序没关系,即:有顺序也行,没有顺序也行!

        而本题要求凑成总和的组合数,元素之间要求没有顺序。所以纯完全背包是能凑成总和就行,不用管怎么凑的。本题是求凑出来的方案个数,且每个方案个数是为组合数。那么本题,两个for循环的先后顺序可就有说法了。

        为了清晰对比,我们对两个for循环的先后遍历顺序讨论一下:

a、外层for循环遍历钱币, 内层for循环遍历金钱总额的情况

for (int i = 0; i < coins.size(); i++) { // 遍历物品(钱币数)
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量(金钱总额),内层循环这里,背包容量必须大于物品大小才有意义,
//这个物品才可以装进背包,所以初始化j=coins[i]
        dp[j] += dp[j - coins[i]];
    }
}

        因为金钱总额遍历在内循环,所以金钱总额里的每一个值只对应了钱币数的单次情况。例如,假设:coins[0] = 1,coins[1] = 2。

        那么就是先把1加入计算,然后再把2加入计算,得到的方法数量只有{1, 2}这种情况。而不会出现{2, 1}的情况。所以这种先物品再背包的遍历顺序中dp[j]里计算的是组合数!

b、把两个for循环的遍历次序交换,先遍历金钱总额,再遍历钱币数

for (int j = 0; j <= amount; j++) { // 遍历背包容量(金钱总额)
    for (int i = 0; i < coins.size(); i++) { // 遍历物品(钱币)
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

        背包容量的每一个值,都是经过 1 和 5 的计算,包含了{1, 5} 和 {5, 1}两种情况。先背包,在物品遍历,此时dp[j]里算出来的就是排列数!

为了进一步分析,我们采用dp五步曲中的第五步来展开讲解:

5)举例dp数组推导

        输入: amount = 5, coins = [1, 2, 5] ,dp状态图如下:

        我们采用先物品再背包的遍历顺序  来求解组合数:

动态规划——零钱兑换问题

         最后 红色框中的结果就是最终的满足条件的组合数。

总结:

动态规划——零钱兑换问题

3、代码

java:

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

python:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount + 1)
        dp[0] = 1
        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        return dp[amount]

----------------------------------------------------------------------------------------------------------------

零钱兑换问题 II

1、原题:力扣原题

动态规划——零钱兑换问题

 (和问题1的区别:问题1是求解满足条件的所有组合数,本题是要求凑成金额的最少硬币个数;其中问题1和问题2的硬币数量都是无限的,即是完全背包问题 的深入)

2、分析

        根据题目要求,最简单的一种思路便是把满足硬币组合等于amount的组合全部列出来,然后找到组合数目最少的即可,可以用递归解决,但时间复杂度会很高,需要很好的剪枝策略;

        另一个直观的想法便是采用动态规划,初始化一个amount+1大小的dp数组,记录每一个状态的最优解,过程如下:

1)dp定义

        dp[j]: 表示 可以凑成金额为j的最少硬币组合个数;

2) dp递归公式

        得到dp[j](考虑coins[i]),只有一个来源,dp[j - coins[i]](没有考虑coins[i])。

        凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])

        所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。递推公式:

        dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

  3)初始化 

        首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;

        其他下标对应的数值呢?

        考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。

4)确定遍历顺序

        动态规划——零钱兑换问题

 故本题,任意顺序遍历都可,我们采用先遍历物品(硬币)再遍历背包(总金额);又因为硬币的个数有无数个,所以为完全背包问题,采用一维dp时,内层循环正序遍历即可

动态规划——零钱兑换问题

3)代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历:完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

python:文章来源地址https://www.toymoban.com/news/detail-440840.html

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        '''版本一'''
        # 初始化
        dp = [amount + 1]*(amount + 1)
        dp[0] = 0
        # 遍历物品
        for coin in coins:
            # 遍历背包
            for j in range(coin, amount + 1):
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return dp[amount] if dp[amount] < amount + 1 else -1

到了这里,关于动态规划——零钱兑换问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II--求组合、组合总和IV--求排列)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(40)
  • 【动态规划】322. 零钱兑换

    定义 要凑出金额n 至少要dp(coins,n)个硬币 确定base case 目标金额为0 返回0 确定 状态 也就是原问题和子问题中的变量,你每次抽取一个硬币,都会导致目标金额减少,所以状态就是目标金额 确定选择,也就是导致状态产生变化的行为,每次选一个硬币都会导致目标金额的减少

    2024年02月10日
    浏览(44)
  • 【面试经典150 | 动态规划】零钱兑换

    【动态规划】【数组】 322. 零钱兑换 定义状态 dp[i] 表示凑成总金额的最少硬币个数。 状态转移 从小到大枚举要凑成的金额 i ,如果当前的金额可以使用面额数组中的某个面额 coin 凑成总金额的一部分,则可以更新 d p [ i ] = m i n ( d p [ i ] , d p [ i − c o i n ] + 1 ) dp[i] = min(dp[i

    2024年04月16日
    浏览(70)
  • 零钱兑换 II(力扣)动态规划 JAVA

    给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 输入:amou

    2024年02月16日
    浏览(42)
  • 零钱兑换 II 力扣(动态规划) JAVA

    给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 输入:amou

    2024年02月15日
    浏览(36)
  • leetcode 动态规划(爬楼梯、零钱兑换、完全平方数)

    卡码网:57. 爬楼梯(opens new window) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表

    2024年01月17日
    浏览(40)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(41)
  • 零钱兑换(Coins Change) -动态规划C语言实现

    1. 前言 零钱兑换是经典的动态规划问题,也是贪心解法不足的反证答案。它要求兑换一定总整数的零钱,满足硬币数量最少的条件。假定我们有3类零钱,构成数组coins[]={1,7,10},现在兑换总额14的金额,如果采用贪心策略,我们有10+1+1+1+1=14, 共需要5枚硬币。实际上本题的最少

    2024年02月09日
    浏览(51)
  • 动态规划part06 518. 零钱兑换 II 377. 组合总和 Ⅳ

     518 零钱兑换|| 377. 组合总和 Ⅳ  

    2024年01月20日
    浏览(46)
  • Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

    题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于:物品是否可以重复使用 思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。 对于完全背包问

    2024年02月20日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包