Nombre minimum de pièces pour constituer un montant en utilisant la récursivité

Question

Le problème est le plus populaire pour illustrer la programmation dynamique, qui est la suivante. Nous avons des pièces de monnaie illimitées de chacune des dénominations 1, 3 et 5. Nous voulons que le nombre minimum de pièces pour obtenir le montant N.

Je suis conscient de la méthode de programmation dynamique où nous construisons une solution à partir de la base cas (s). Mais je voulais voir comment écrire une solution purement récursive. Je suis capable de travailler facilement à la main pour N = 11 et dénominations = [1,3,5]. Mais pour une raison quelconque, je suis incapable de faire le travail suivant.

def minNumberOfCoins(amount, denominations): 
     if amount <= 0: 
      return(0) 
     if amount in denominations: 
      return(1) 
     else: 
      listToExamine = list(filter(lambda x: x > 0, map(lambda x: amount - x, denominations))) 
      print(listToExamine) 
      minVal = min(listToExamine, key=lambda x: 1 + minNumberOfCoins(x, denominations)) 
      return(minVal) 

Pour autant que je sache, la logique est identique à ce que j'ai élaboré sur papier. Y a-t-il une nuance dans la récursivité de Python que je ne connais pas, ou y a-t-il quelque chose de subtil qui me manque? Je vous remercie!

Answer 1

Cette mise en œuvre semble plus simple:

def minNumberOfCoins(amount, denominations): 

    if amount <= 0: 
     return(0) 

    if amount in denominations: 
     return(1) 

    for d in sorted(denominations, reverse=True): 
     if d <= amount: 
      return 1 + minNumberOfCoins(amount - d, denominations) 

Answer 2

Une approche plus lisible. Vous ne devriez pas mélanger map ou filter avec beaucoup de lambdas. Les compréhensions conditionnelles et les générateurs sont généralement les meilleurs choix:

def min_coins(amount, denominations): 
    # these two base cases seem to cover more edge cases correctly 
    if amount < 0: 
     return None 
    if amount == 0: 
     return 0 
    tries = (min_coins(amount-d, denominations) for d in denominations) 
    try: 
     return 1 + min(t for t in tries if t is not None) 
    except ValueError: # the generator in min produces no values 
     return None 

min_coins(11, [1,3,5]) 
# 3