python 递归 找零钱

Question

def coins_changeREC(coin_values, change):
    min_count = change 
    
    if change in coin_values:
        return 1
    for value in [i for i in coin_values if i <= change]:
        count = 1 + coins_changeREC(coin_values, change-value)
        if count < min_count:
            min_count = count
    return min_count

不太理解，求大佬解释一下

if count < min_count:
            min_count = count

Answer 1

首先回答你的问题

count = 1 + coins_changeREC(coin_values, change-value)#1.when reached here, one recursion link ends
        if count < min_count: 
            min_count = count #2. update the minimum count of coins

每次走到注释1的地方的时候，对于一个coin_value开始的递归链已经结束并得到了总数。
这段代码意思是在对于每个面额硬币开始的递归过程中，不断维护min_count这个变量，使其为所有可能性组合中最小的硬币数目。但是如果一开始不给min_count赋值，那就需要在第一次有得到count值的时候，额外增加判断min_count是否有值的逻辑，如果有，和min_count比较，两者中较小值，如果无值，将count赋给min_count。而总额的数目比如20，比如50，肯定大于等于需要的硬币数，所以min_count值是个很好的初始值，只要无脑把count和min_count中较小值赋值给min_count就好了。
如果不给min_count初始值，则代码大致为：

def coins_changeREC(coin_values, change):
    min_count = None     
    if change in coin_values:
        return 1
    for value in [i for i in coin_values if i <= change]:
        count = 1 + coins_changeREC(coin_values, change-value)
        if min_count is None:
            min_count = count
        else:
            min_count = min(min_count,count)
    return min_count

一点ps：

1. 递归代码的思路比较反人类，想不清楚的时候可以画出递归的路径，也能帮你看出重复的递归路径，为日后进阶到动态规划打好基础。
2. 这个代码在暴力递归解法中也是效率较低的，每次都要生产新的list，可以遍历原有的list，通过if筛选比change总数小的值的硬币就可以了。

Answer 2

简单的讲，就是遍历所有可能找钱的方案，找到最小的 min_count, 然后返回。

复杂点讲：

1. 这是一个递归的代码
2. 你也可以理解为一个树，这个树里面每个节点是找的一个零钱。然后算这个树的高度最矮的高度是多少。

---

欢迎关注公众号：搬砖程序员带你飞