> 文档中心 > Python每日一练-----零钱兑换

Python每日一练-----零钱兑换

🌧(day50:P47)

目录

📝题目:

🚩题目分析:

💡解题思路:

🌟解法一:递归

🌈代码实现

✏代码注释

🌟解法二:

🌈代码实现

✏代码注释


📝题目:

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

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

⭐示例 1:

输入:coins = [1, 2, 5], amount = 11

输出:3

解释说明:11 = 5 + 5 + 1

⭐示例 2:

输入:coins = [2], amount = 3

输出:-1

解释说明:硬币无法凑成金额-1

⭐示例 3:

输入:coins = [1], amount = 0

输出:0

🚩题目分析:

题目要求用最少的硬币个数凑出总金额amount。我们第一感觉可能是使用暴力或者递归解题,对这道题使用暴力解题,计算出所有可能的结果后取硬币数最小值,时间复杂度妥妥O(n^3),算是很慢的解题方式了,下面我们介绍递归解法和玄学位运算解法(使用到位运算解法的解题效率一半很高,但是很难想到,所以我愿称之为“玄学”)

💡解题思路:

🌟解法一:递归

使用动态规划五部曲

✨1.分析确定dp数组以及其下标的含义或状态分析

我们规定dp[i]表示凑足总额为  i  所需钱币的最少个数。

✨2.确定递推公式 

我们考虑dp[i]的来源,因为dp[i]的来源为dp[i - coins[i]] + 1,(coins[i]表示coins中的第i枚硬币),这也是dp[i]的唯一来源。

那为什么要+1呢?

这里我们明确dp[i - coins[i]]是凑够金额 i - coin[i]的最少硬币个数。那么当金额i - coin[i]变到 i 时,意味着我们在coins中拿了一枚硬币coins[i],那么从dp[i - coin[i]] 到 dp[i]需要加上所取得那枚硬币,即+1.

分析到dp[i]状态及前面得状态,dp[i]即为最优解。

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

coins = [1, 2, 3]   amount = 5

那么在 1+1+1+1+1 = 5, 1+2+1+1 = 5, 2+2+1 = 5....等情况中

dp[5]最优解必为2+2+1 = 5

即dp[5] = dp[5 - coins[0]] + 1 

而dp[5 - coins[0]] = dp[4] = dp[4 - coins[1]] + 1

以此类推

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

我们要取最优解(硬币数最少)也就是取dp[i - coins[i]] + 1最小值

即递推公式为:dp[i] = min(dp[i - coins[i]] + 1, dp[i])

(括号中得dp[i]为上一状态的dp[i])

✨3.如何初始化dp数组

我们分析公式的基础,可得公式基础为dp[0]即凑足总额为  0  所需钱币的最少个数。接着考虑到其他dp列表其他下标的初始化,由于递推公式使用了min(),那么为了不让初始化影响递推结果,我们需要将dp[i](i != 0)初始化为一个很大的数,如正无穷‘inf’。

4.确定遍历的顺序

题目要求的是找到最小硬币个数,所以遍历coins或者先遍历寻找amount列表无关紧要。

✨5.举例验证推导的dp数组(公式)是否正确

可以带入一个简单以的例子,比如例1.

🌈代码实现

def coinChange(coins, amount):    dp = [float('inf')] * (amount + 1)    dp[0] = 0    for coin in coins: for i in range(coin, amount + 1):     dp[i] = min(dp[i], dp[i - coin] + 1)    return dp[amount] if dp[amount] != float('inf') else -1

✏代码注释

def coinChange(coins, amount):    # 初始化dp列表    dp = [float('inf')] * (amount + 1)    dp[0] = 0  # 初始化递推公式基础    for coin in coins:   # 遍历硬币 # 遍历寻找构成amount最优解 for i in range(coin, amount + 1):dp[i] = min(dp[i], dp[i - coin] + 1)    # 如果最终没有找到凑成amount金额的硬币,返回-1    return dp[amount] if dp[amount] != float('inf') else -1

时间复杂度O(nm),n为amoun面额,m为硬币种数。空间复杂度为O(m),即为dp列表所用空间。

🌟解法二:

接下来就是玄学位运算了。先看代码

🌈代码实现

def coinChange(coins, amount):    if not amount: return 0    dp = 1 <> i if tmp & 1:     return res dp = tmp    return -1

✏代码注释

def coinChange(coins, amount):    if not amount: return 0    # 按位左移运算构造类似dp数组的记录二进制    dp = 1 <> i if tmp & 1:  # 当tmp最后位数为1时res即为答案,返回res     return res dp = tmp    return -1

位运算解法过程我打印出来了,不清楚的可以看看

def coinChange(coins, amount):    if not amount: return 0    dp = 1 <> i     print('ys_tmp:', bin(tmp))     print('--------------') if tmp & 1:     return res dp = tmp    return -1

输出

dp: 0b100000000000tmp: 0b0res: 1i: 1ys_tmp: 0b10000000000--------------i: 2ys_tmp: 0b11000000000--------------i: 5ys_tmp: 0b11001000000--------------dp: 0b11001000000tmp: 0b0res: 2i: 1ys_tmp: 0b1100100000--------------i: 2ys_tmp: 0b1110110000--------------i: 5ys_tmp: 0b1110110010--------------dp: 0b1110110010tmp: 0b0res: 3i: 1ys_tmp: 0b111011001--------------i: 2ys_tmp: 0b111111101--------------i: 5ys_tmp: 0b111111101--------------

虽然难理解,但是解题效率不是一般的高

时间复杂度O(n),n为coins长度。空间复杂度O(1),使用有限变量。

了解更多位运算:还在为原码、反码、补码和位运算搞得头昏脑涨?点这里,还你清析脑回路

了解更多动态规划:团灭动态规划经典-----买卖股票最佳时机问题

今天就到这,明天见。🚀

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄