Algorithme: Changement de monnaie - Compter le nombre de façons dont on peut changer

J'essaie de comprendre le DP derrière le problème du changement de monnaie, où l'on est censé compter le nombre de façons dont vous pouvez donner le changement pour une dénomination étant donné un ensemble de pièces de monnaie. Chaque pièce est présente un nombre infini de fois.Algorithme: Changement de monnaie - Compter le nombre de façons dont on peut changer

L'algorithme est tiré de la page this geeks4geeks. Les algorithmes sont les suivants (où N représente la dénomination et dp est un tableau de taille N + 1):

dp[0] = 1 
for each coin c: 
    for i from c to N: 
     if i >= c: 
      dp[i] += dp[i-c]

Je ne suis pas en mesure de comprendre comment est le DP travailler ici et quelles sont les sous-problèmes. Editer: J'ai coché d'autres questions, mais aucune ne mentionne l'algorithme indiqué ci-dessus. Une solution de DP bidimensionnelle est abordée dans les questions précédentes.

Source

2017-06-23 user3667569

Cet algorithme est une simplification de l'algorithme DP 2D précédent donné dans ce lien. Si vous regardez la façon dont vous faites référence à d'autres indices dans l'algorithme précédent, il devrait être facile de voir qu'il peut être simplifié de cette manière. Il ne s'agit pas tant de penser en termes de sous-problèmes que de penser en termes de simplification. – Dukeling

Eh bien, je ne suis pas capable de comprendre la simplification et c'est pourquoi j'ai demandé de l'aide. Merci! – user3667569

Fondamentalement, 'table [:]' dans le second est 'table [:] [j]' dans le premier. Le reste est le même. Ils ont changé les indices, ce qui pourrait rendre les choses confuses. Il n'est pas rare dans DP de remarquer que vous ne regardez qu'une seule ligne en arrière et que vous n'avez donc pas besoin de stocker la matrice entière, parfois vous stockez la dernière rangée et la dernière, mais vous pouvez simplement l'écraser au fur et à mesure. – Dukeling

Vous pouvez considérer cette approche comme résolvant des sous-problèmes C où C est le nombre de pièces.

Le sous-problème c est composé de «Quelles valeurs peuvent être faites à partir de pièces de monnaie jusqu'à et y compris la pièce c, mais ne comprennent pas les pièces de plus grande valeur».

Le sous-problème de base devient alors « Quelles valeurs peut être faite de pas de pièces », à laquelle la réponse est juste la valeur 0.

ensuite de travailler sur chaque sous-supplémentaire, nous pouvons itérer les valeurs de marquage tableau comme possible si elles sont constituées d'une valeur faite à partir des valeurs de pièces précédentes plus un certain nombre de pièces de monnaie de la valeur actuelle. Comme nous mettons à jour la matrice DP sur place, il s'avère que nous devons seulement ajouter une pièce de monnaie de la valeur actuelle pour chaque emplacement dans la matrice.

Source

2017-06-23 18:58:45

Algorithme: Changement de monnaie - Compter le nombre de façons dont on peut changer

Répondre

Questions connexes