当前位置:   article > 正文

深入浅出算法题-零钱兑换的动态规划问题

零钱兑换算法

点击上方“摸鱼吧算法工程师”卡片,关注星标

获取有趣、好玩的前沿干货!

一、 零钱兑换:硬币的最少个数

  • 给一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

  • 计算并返回可以凑成总金额所需的最少硬币个数 。如果没有任何一种硬币组合能组成总金额,返回-1 。

  • 可认为每种硬币的数量是无限的。

44c7f29d5b54d37c3aba765567840e2c.png

解题关键点

  • 经典的动态规划问题。

  • 设置一个数组dp,其中每个元素dp[i]记录的是,当金额为i时,所需要的硬币个数。则题目所求为dp[amount]。

  • 考虑基础简单的例子。有dp[0] = 0,也就是说,金额为0所需的硬币个数是0。

  • 考虑状态转移公式。从小到大遍历金额数,这样,可以保证:当我们计算金额i所需的最少硬币个数dp[i]时,前面更少的金额所需要的最少硬币个数,比如dp[i-1]、dp[i-2]······等都已求出。

  • 那么,对任意的dp[i],面对某种硬币的面额(记为coin),如果在凑成金额i时选择了这枚硬币,那么在凑成金额(i-coin)时所需要的硬币个数 + 1即可。也就是dp[i] = dp[i-coin] + 1。

  1. class Solution(object):
  2.     def coinChange(self, coins, amount):
  3.         """
  4.         :type coins: List[int]
  5.         :type amount: int
  6.         :rtype: int
  7.         """
  8.         # 初始化为正无穷大
  9.         dp = [float('inf')]*(amount+1)
  10.     
  11.         # 金额为0,所要凑的硬币个数也为0
  12.         dp[0] = 0
  13.         
  14.         for coin in coins:
  15.             sum_coin = coin
  16.             
  17.             while sum_coin < (amount+1):
  18.                 dp[sum_coin] = min(dp[sum_coin], dp[sum_coin-coin]+1)
  19.                 sum_coin += 1
  20.         
  21.         # print(dp)
  22.         return dp[amount] if dp[amount]!= float('inf'else -1

二、零钱兑换:硬币的组合总数

  • 给一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

  • 计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

  • 假设每一种面额的硬币有无限个。

8f8789e960fc0c811d65bd1ebd50418e.png

解题关键点

  • 经典的动态规划问题。

  • 设置一个数组dp,其中每个元素dp[i]记录的是,当凑成金额为i时,所有的硬币组合的总数。则题目所求为dp[amount]。

  • 考虑基础简单的例子。有dp[0] = 1,也就是说,金额为0时,只有1种选择,就是什么硬币都不取。

  • 考虑状态转移公式。从小到大遍历金额数,这样,可以保证:当我们计算金额i的硬币组合数dp[i]时,前面更少的金额的组合数比如dp[i-1]、dp[i-2]······等都已求出。

  • 那么,对任意的dp[i],面对某种硬币的面额(记为coin),如果在凑成金额i时选择了这枚硬币,那么它也包含了凑成金额(i-coin)时的组合个数。而对不同面值的硬币coin,都需要累加所有的组合个数。

  1. class Solution(object):
  2.     def change(self, amount, coins):
  3.         """
  4.         :type amount: int
  5.         :type coins: List[int]
  6.         :rtype: int
  7.         """
  8.         dp = [0]*(amount+1)
  9.         dp[0] = 1
  10.         for coin in coins:
  11.             sum_coin = coin
  12.             
  13.             while sum_coin <= amount:
  14.                 dp[sum_coin] += dp[sum_coin-coin]
  15.                 sum_coin += 1
  16.         
  17.         return dp[amount]

本文仅作学术分享  侵删

-------------END-------------

往期阅读

深入浅出算法题(1)-动态规划前n个数字二进制中1的个数

深入浅出算法题(2)-回文子串个数之马拉车算法

(1)GAN改进系列 | 最新ICCV2021生成对抗网络GAN论文梳理汇总

(2)最新ICCV 2021 | 图像转换生成对抗GAN汇总梳理

最新 ICCV 2021 | GAN隐私保护(33)医学图像(34)生成对抗GAN

最新 ICCV 2021 论文推荐

【附下载】机器学习统计学,476页pdf

【附下载】《面向机器学习的特征工程》.pdf

【收藏】机器学习核心概念完全解析

【附ppt与视频】可解释机器学习进展,附ppt与视频

2d1836b813c857884428777f6e965291.png

如果觉得有用,就点个“在看”吧 77250209e66b7a9b6633ec7c2c600339.png

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/243812
推荐阅读
相关标签
  

闽ICP备14008679号