python中此程序的意外行为

Question

我有这个代码来计算最小数量的硬币从一个总和与给定的名单表示。 例如：minimum change for 69 with denomiations [25,10,5,1] : [25, 25, 10, 5, 1, 1, 1, 1]

def get_min_coin_configuration(sum=None, coins=None, cache={}):
    #if cache == None:  # this is quite crucial if its in the definition its presistent ...
    #    cache = {}
    if sum in cache:
        return cache[sum]
    elif sum in coins:  # if sum in coins, nothing to do but return.
        cache[sum] = [sum]
        return cache[sum]
    elif min(coins) > sum:  # if the largest coin is greater then the sum, there's nothing we can do.
        #cache[sum] = []
        #return cache[sum]
        return []
    else:  # check for each coin, keep track of the minimun configuration, then return it.
        min_length = 0
        min_configuration = []
        for coin in coins:
            results = get_min_coin_configuration(sum - coin, coins, cache)
            if results != []:
                if min_length == 0 or (1 + len(results)) < len(min_configuration):
                    #print "min config", min_configuration
                    min_configuration = [coin] + results
                    #print "min config", min_configuration
                    min_length = len(min_configuration)
                    cache[sum] = min_configuration
        return cache[sum]
if __name__ == "__main__":
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1])
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1])

当我注释掉main中的任何一个print语句时，程序似乎运行良好。 当我有两个函数调用时，它打印错误。在main中注释掉print语句，你就会看到它正确地打印出最小的硬币。你知道吗

minimum change for 69 with denomiations [25,10,5,1] by recursive :  [25, 25, 10, 5, 1, 1, 1, 1]
*********************************************
minimum change for 7 with denomiations [4,3,1] by recursive :  [5, 1, 1]

Answer 1

if __name__ == "__main__":
    cache_denom_set1 = {}
    cache_denom_set2 = {}
    print "minimum change for 69 with denomiations [25,10,5,1] by recursive : ",get_min_coin_configuration(69,[25,10,5,1],cache_denom_set1)
    print "*"*45
    print "minimum change for 7 with denomiations [4,3,1] by recursive : ",get_min_coin_configuration(7,[4,3,1],cache_denom_set2)

为每组面额传入一个单独的缓存

问题是，缓存已经知道如何将7更改为5,1,1，所以它只返回。。。缓存不知道5已不在面值集中。。。你知道吗

字典就像列表一样是可变的。。。这应该说明问题所在

def dict_fn(cache={}):
    cache[len(cache.keys())] = 1
    print cache

dict_fn()
dict_fn()