Escaliers et combinaisons de pièces
Construire des récurrences classiques en une dimension
Escaliers et combinaisons de pièces est une leçon Coding Interview Prep 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Découvrez l'escalade d'escaliers
Vous pouvez monter de 1 ou de 2 marches à la fois. Combien de façons permettent d'atteindre la marche n ? Ce grand classique du DP 1D n'est autre que la suite de Fibonacci sous une autre forme.
Trouvez la récurrence
Pour vous trouver sur la marche i, vous veniez de i-1 ou de i-2. Ainsi, dp[i] = dp[i-1] + dp[i-2] : on additionne les deux derniers déplacements possibles.
dp[i] = dp[i-1] + dp[i-2]Définissez les cas de base
Il existe une façon de rester au sol et une façon d'atteindre la marche 1. Ces cas de base initialisent toute la table.
dp[0], dp[1] = 1, 1Remplissez la table et lisez la réponse
Parcourez les marches vers le haut : la dernière case contient le nombre recherché. La solution complète tient dans une petite boucle de tabulation.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Réduisez à deux variables
Vous n'avez besoin que des deux dernières valeurs, vous pouvez donc supprimer le tableau. Cette version en espace O(1) est très appréciée en programmation compétitive.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bPassez aux combinaisons de pièces
Étant donné des valeurs de pièces, comptez les façons d'obtenir le montant A. L'ordre n'aura pas d'importance ici : nous comptons des combinaisons, et non des séquences.
coins = [1, 2, 5]La table des combinaisons
Soit dp[x] le nombre de façons de former x. Commencez par une façon de former zéro : l'ensemble vide de pièces.
dp = [0]*(A+1)
dp[0] = 1Placez la boucle des pièces à l'extérieur
Placez la boucle des pièces à l'extérieur de la boucle des montants. Cet ordre compte chaque combinaison exactement une fois, jamais les permutations.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Combinaisons ou permutations
Inversez l'ordre des boucles et vous compterez à la place les façons ordonnées. Le simple imbrication des boucles suffit à modifier le sens de la réponse.
Variante : changement de pièces minimal
Pour obtenir le moins de pièces possible, stockez un minimum plutôt qu'une somme. Initialisez avec l'infini et prenez 1 plus la meilleure sous-problème.
dp[x] = min(dp[x], dp[x-c] + 1)Un motif, plusieurs apparences
Les escaliers et les pièces ont la même structure : chaque état additionne ou minimise quelques états précédents. Repérez cette structure et le code s'écrit presque tout seul.
Vérification rapide
Pour compter les combinaisons de pièces, quel ordre de boucles évite les doublons ?
Récapitulatif : additionnez les derniers déplacements
Vous pouvez maintenant résoudre les problèmes d'escaliers et de comptage de pièces avec une récurrence 1D. Chaque réponse additionne quelques états antérieurs, et l'ordre des boucles distingue les combinaisons des permutations.
Apprends Coding Interview Prep avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 90
- Leçons
- 360
Questions Fréquemment Posées
La leçon « Escaliers et combinaisons de pièces » est-elle gratuite ?
Oui — le texte complet de « Escaliers et combinaisons de pièces » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Escaliers et combinaisons de pièces » ?
Construire des récurrences classiques en une dimension Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep 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 « Escaliers et combinaisons de pièces » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep 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
- Mémoïsation contre tabulation
- Définir l’état et la transition
- Escaliers et combinaisons de pièces
- Plus longue sous-séquence croissante