这是一个很大的算法问题，但老实说，我认为您的实现不正确，或者很抱歉，我可能不了解您函数的输入/输出。
这是实现的修改版本。
def C(i, coins, cdict = None): if cdict == None: cdict = {} if i <= 0: cdict[i] = 0 return cdict[i] elif i in cdict: return cdict[i] elif i in coins: cdict[i] = 1 return cdict[i] else: min = 0 for cj in coins: result = C(i - cj, coins) if result != 0: if min == 0 or (result + 1) < min: min = 1 + result cdict[i] = min return cdict[i]这是我尝试解决类似问题的尝试，但是这次返回了硬币列表。我最初从递归算法开始，该算法接受一个总和和一个硬币列表，如果找不到这种配置，它可能返回一个硬币数量最少的列表，或者返回无。
def get_min_coin_configuration(sum = None, coins = None):if sum in coins: # if sum in coins, nothing to do but return. return [sum]elif max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do. return Noneelse: # check for each coin, keep track of the minimun configuration, then return it. min_length = None min_configuration = None for coin in coins: results = get_min_coin_configuration(sum = sum - coin, coins = coins) if results != None: if min_length == None or (1 + len(results)) < len(min_configuration): min_configuration = [coin] + results min_length = len(min_configuration) return min_configuration
好的，现在让我们看看是否可以通过使用动态编程（我称之为缓存）来改善它。
def get_min_coin_configuration(sum = None, coins = None, cache = None):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 max(coins) > sum: # if the largest coin is greater then the sum, there's nothing we can do. cache[sum] = None return cache[sum]else: # check for each coin, keep track of the minimun configuration, then return it. min_length = None min_configuration = None for coin in coins: results = get_min_coin_configuration(sum = sum - coin, coins = coins, cache = cache) if results != None: if min_length == None or (1 + len(results)) < len(min_configuration): min_configuration = [coin] + results min_length = len(min_configuration) cache[sum] = min_configuration return cache[sum]现在让我们运行一些测试。
assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in[({'sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]), ({'sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]), ({'sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]), ({'sum':123, 'coins':[5, 10, 25]}, None), ({'sum':100, 'coins':[1,5,25,100]}, [100])] ])如果此测试不够强大，您也可以这样做。
import randomrandom_sum = random.randint(10**3, 10**4)result = get_min_coin_configuration(sum = random_sum, coins = random.sample(range(10**3), 200))assert sum(result) == random_sum
没有这样的硬币组合可能等于我们的random_sum，但我相信它的可能性很小…
我肯定那里有更好的实现方式，我试图强调可读性而不是性能。祝好运。
更新
了先前的代码，它有一个小错误，它应该检查最小硬币而不是最大硬币，重新编写符合pep8标准的算法，并
[]在找不到组合的情况下返回代替
None。
def get_min_coin_configuration(total_sum, coins, cache=None): # shadowing python built-ins is frowned upon. # assert(all(c > 0 for c in coins)) Assuming all coins are > 0 if cache is None: # initialize cache. cache = {} if total_sum in cache: # check cache, for previously discovered solution. return cache[total_sum] elif total_sum in coins: # check if total_sum is one of the coins. cache[total_sum] = [total_sum] return [total_sum] elif min(coins) > total_sum: # check feasibility, if min(coins) > total_sum cache[total_sum] = [] # no combination of coins will yield solution as per our assumption (all +). return [] else: min_configuration = [] # default solution if none found. for coin in coins: # iterate over all coins, check which one will yield the smallest combination. results = get_min_coin_configuration(total_sum - coin, coins, cache=cache) # recursively search. if results and (not min_configuration or (1 + len(results)) < len(min_configuration)): # check if better. min_configuration = [coin] + results cache[total_sum] = min_configuration # save this solution, for future calculations. return cache[total_sum]assert all([ get_min_coin_configuration(**test[0]) == test[1] for test in [({'total_sum':25, 'coins':[1, 5, 10]}, [5, 10, 10]), ({'total_sum':153, 'coins':[1, 5, 10, 50]}, [1, 1, 1, 50, 50, 50]), ({'total_sum':100, 'coins':[1, 5, 10, 25]}, [25, 25, 25, 25]), ({'total_sum':123, 'coins':[5, 10, 25]}, []), ({'total_sum':100, 'coins':[1,5,25,100]}, [100])] ])
