DP non bornée et rendu de monnaie
Utiliser les éléments autant de fois que nécessaire
DP non bornée et rendu de monnaie est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Objets disponibles en quantité illimitée
Dans le sac à dos non borné, chaque objet peut être pris autant de fois que vous le souhaitez. Pensez aux pièces d'un distributeur automatique, et non à un stock limité.
Le minuscule changement
Par rapport au problème 0/1, seule la direction de la boucle change. Pour des objets non bornés, parcourez la capacité vers l'avant, de la plus petite valeur à la plus grande.
La réutilisation vers l'avant est le principe
En avançant, dp[w - coin] peut déjà inclure cette même pièce. Cette réutilisation intentionnelle permet précisément de la prendre à nouveau.
Découvrez le problème du rendu de monnaie
Le classique problème du rendu de monnaie demande le plus petit nombre de pièces dont la somme atteint un montant. Il s'agit d'un DP non borné qui utilise un minimum au lieu d'un maximum.
Définissez l'état
Soit dp[a] le nombre minimal de pièces nécessaires pour former le montant a. Commencez par dp[0] = 0, puisque zéro ne nécessite aucune pièce.
dp = [float("inf")] * (amount + 1)
dp[0] = 0Utilisez l'infini pour les montants impossibles
Les montants inaccessibles commencent à l'infini. Si un montant reste infini à la fin, aucune combinaison de pièces ne permet de le former.
La transition
Pour chaque pièce, essayez d'améliorer chaque montant qu'elle peut atteindre. Utilisez une pièce de plus que le montant plus petit restant.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] = min(dp[a], dp[a - coin] + 1)Pourquoi l'ordre croissant
Parcourir les montants dans l'ordre croissant permet à dp[a - coin] de compter déjà cette pièce. C'est ainsi qu'une seule pièce peut contribuer plusieurs fois.
Comptez plutôt les façons
Remplacez min+1 par une somme pour compter le nombre de façons de former chaque montant. La boucle des pièces à l'extérieur évite de compter deux fois les ordres différents.
for coin in coins:
for a in range(coin, amount + 1):
dp[a] += dp[a - coin]Lisez le résultat
Votre réponse se trouve dans dp[amount]. Dans la version avec minimum, une valeur infinie signifie qu'il est impossible de former la cible.
0/1 ou non borné
Retenez cette seule différence : une capacité parcourue en sens inverse signifie que chaque objet est utilisé une fois, tandis qu'un parcours vers l'avant signifie une quantité illimitée. Même table, parcours opposé.
Vérification rapide
Vérifiez ce qui rend le sac à dos non borné.
Récapitulatif
Vous avez inversé la boucle pour permettre la réutilisation illimitée et construit le rendu de monnaie avec un minimum pour le moins de pièces possible, ou une somme pour le nombre total de façons. 💰
Questions Fréquemment Posées
La leçon « DP non bornée et rendu de monnaie » est-elle gratuite ?
Oui — le texte complet de « DP non bornée et rendu de monnaie » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « DP non bornée et rendu de monnaie » ?
Utiliser les éléments autant de fois que nécessaire Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « DP non bornée et rendu de monnaie » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Sac à dos 0/1 : prendre ou laisser
- Sac à dos optimisé en espace
- DP non bornée et rendu de monnaie
- Somme de sous-ensemble et partition