动态规划问题：零钱兑换的递归、备忘录、动态规划解法（Python）_钱币兑换问题递归

零钱兑换问题

有不同面额的硬币coin（需要你的输入）
和总金额amount
计算可以凑出总金额所需的最少硬币个数
如果有解则返回所需硬币个数
如果无解则返回-1

eg：
输入：[1,2,5] 11
输出：3
1
2
3

解释

这是一个寻找最优解的问题
我们有两种方法：

• 第一种：遍历出所有的可能性，然后寻找出它的最优解，暴力解法
• 第二种：动态规划

在后续的考究中，动态规划无论是时间复杂度还是算法复杂度都要远好于暴力破解

方法一：普通递归 纯暴力破解（会超时）

def coinChange(coins,amount):
    #如果当前的金额数为0，那么就不需要硬币了
    if amount==0:
        return 0
    #如果当前的金额数为负数，那么久凑不出来
    if amount<0:
        return -1
    #我们设置一个非常非常大的数，来比较和第一个遍历情况所需硬币数的大小
    #这里可能难以理解
    #是这样的，比如你的第一种情况是4个，但是你又不好保存下来，因为它在递归树里面，所以用一个超大的数把第一个结果保存
    #之后再不停得递归，永远和当前最小值进行比较
    #就可以获得全局最小值
    res=10000000
    #开始递归面值
    for i in coins:
        #这个递归的详细解读就是，先遍历到最底部，让amount慢慢长大
        #在amount长大的过程中如果刚好有这样的面额，就把它赋值给subProlem
        #比如在i==1的时候，我们amount也是1，那么就返回0，表示不需要额外的硬币了
        #比如在i==1的时候我们的amount是2，这时候subProblem就是2了
        #但是在我们遍历i==2的时候，这个时候的amount还是2，但是这个时候的subProblem 就是0了
        #明显最优解是给面值为2的钞票
        subProblem=coinChange(coins,amount-i)
        
        # subProblem为-1的情况就是实在是没法给钞票的情况
        if subProblem==-1:
            continue
        #这里需要额外加1，因为一开始我们都是用返回值为0表示不需要额外的硬币，但是这个时候已经花了硬币除去了
        res=min(res,subProblem+1)

    if res==10000000:
        return -1
    else:
        return res
print(coinChange([1,2,5],11))

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

递归比较复杂
当然有递归就有备忘录解法
来减少时间复杂度

方法二：备忘录递归解法（暴力）

def coinChange(coins,amount):
    #全局变量，备忘录
    global memo
    #将备忘录所有的值都设置成一个比较“离谱”的值
    memo=[-100 for i in range(amount+1)]
    return dp(coins,amount)
def dp(coins,amount):
    if amount==0:
        return 0
    if amount<0:
        return -1
    #如果备忘录里面有数据，就读取备忘录
    if memo[amount]!=-100:
        return memo[amount]

    res=10**10
    for i in coins:
        subProblem=dp(coins,amount-i)
        if subProblem==-1:
            continue
        res=min(res,subProblem+1)
    #把结果存到备忘录
    if res==10**10:
        memo[amount]=-1
    else:
        memo[amount]=res
    return memo[amount]
#这里备忘录的作用就是记录功能
#可以说，比如我有amount==11的时候
#但是我肯定要经历amount==3的时候
#这个时候备忘录记录这我amount==3的时候的最小硬币个数是2，我就可以直接用了，不需要再递归遍历
#再比如我amount==5，这个时候备忘录里面记录了1,2,3,4没有记录5，这个5就要被记录下来
print(coinChange([1,2,5],11))
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

方法三：动态规划

我认为动态规划理解起来要比递归容易得多

def coinChange(coins,amount):
    #弄一个dp数组，这个值不能胡乱设置，比如-100就不可以，因为后面要做最小值比较
    #amount+1表示最不可能出现的情况，比如我金额为11，那么这个里面我用12枚硬币就是最不可能出现的情况
    dp=[amount+1 for _ in range(amount+1)]
    #因为我想要的是按照金额就是其对应的索引下标
    #金额为0的时候自然就不需要硬币
    dp[0]=0

    #去遍历这个数组
    for i in range(len(dp)):
        #遍历面值，所有的要一个一个试试
        for coin in coins:
            #如果这个面值大于了现在所剩下的金额，就不用这个面值
            if i-coin<0:
                continue
            #这里的1+dp[i-coin]是因为减去了当前的coin，这面值还没算进去
            dp[i]=min(dp[i],1+dp[i-coin])
            
    #如果查询还是原来的数值，那就没有成功
    if dp[amount]==amount+1:
        return -1
    else:
        return dp[amount]

print(coinChange([1,2,5],11))
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

此时我的i==3，coin ==5
那么5的面值太大了，所以continue

i==4 coin ==1
dp[4]==12
dp[4-1]==2
之后再加1可以知道这个时候用三个硬币就可以把面值为4的给存储

主要是之前我们已经存储了面值为3的时候所需要的硬币数

但是这个时候你会发现，好像两个面值为2的硬币情况更好
所以把3替换成2

自己去调试一下代码其实就很简单了
推荐pycharm