Python零钱兑换的实现代码

目录

• 题目：
• 题目分析：
• 解题思路：
• 解法一：递归
• 代码实现
• 代码注释
• 解法二：

题目：

给你一个整数数组 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 << amount
    res = 0
    while dp:
        tmp = 0
        res += 1
        for i in coins:
            tmp |= dp >> i
        if tmp & 1:
            return res
        dp = tmp
    return -1

代码注释

def coinChange(coins, amount):
    if not amount:
        return 0
    # 按位左移运算构造类似dp数组的记录二进制
    dp = 1 << amount
    res = 0
    while dp:  # dp = 0或return 时循环结束
        tmp = 0  # tmp用于临时记录和承接上一个dp二进制
        res += 1  # res为最终答案
        for i in coins:
            # 利用按位右移不断右移。利用按位或运算
            # 将前一次按位右移运算与后一次按位右移运算合并
            tmp |= dp >> 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 << amount
    res = 0
    while dp:
        print('dp:', bin(dp))
        tmp = 0
        print('tmp:', bin(tmp))
        res += 1
        print('res:', res)
        for i in coins:
            print('i:', i)
            tmp |= dp >> i
            print('ys_tmp:', bin(tmp))
            print('--------------')
        if tmp & 1:
            return res
        dp = tmp
    return -1

输出

dp: 0b100000000000
tmp: 0b0
res: 1
i: 1
ys_tmp: 0b10000000000
————–
i: 2
ys_tmp: 0b11000000000
————–
i: 5
ys_tmp: 0b11001000000
————–
dp: 0b11001000000
tmp: 0b0
res: 2
i: 1
ys_tmp: 0b1100100000
————–
i: 2
ys_tmp: 0b1110110000
————–
i: 5
ys_tmp: 0b1110110010
————–
dp: 0b1110110010
tmp: 0b0
res: 3
i: 1
ys_tmp: 0b111011001
————–
i: 2
ys_tmp: 0b111111101
————–
i: 5
ys_tmp: 0b111111101
————–

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

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