Trappen beklimmen en muntcombinaties
Klassieke 1D-recursies vanaf nul opbouwen
Trappen beklimmen en muntcombinaties is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 3 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Maak kennis met Traplopen
Je kunt per keer 1 of 2 treden nemen. Op hoeveel manieren bereik je trede n? Deze klassieke 1D-DP is eigenlijk Fibonacci in vermomming.
Vind de recursie
Om op trede i te staan, kwam je vanaf i-1 of i-2. Dus dp[i] = dp[i-1] + dp[i-2]: je telt beide laatste stappen op.
dp[i] = dp[i-1] + dp[i-2]Stel de basisgevallen in
Er is één manier om op de grond te blijven en één manier om trede 1 te bereiken. Deze basisgevallen vormen de basis voor de hele tabel.
dp[0], dp[1] = 1, 1Vul de tabel in en lees het antwoord
Doorloop de treden van beneden naar boven en de laatste cel bevat de telling. De volledige oplossing is een kleine tabelinvullus.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Verklein naar twee variabelen
Je hebt alleen de laatste twee waarden nodig, dus je kunt de array weglaten. Deze versie met O(1) geheugen is favoriet in programmeerwedstrijden.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bStap over op muntcombinaties
Gegeven muntwaarden tel je het aantal manieren om bedrag A te maken. De volgorde doet er hier niet toe, dus tellen we combinaties, geen reeksen.
coins = [1, 2, 5]De combinatietabel
Laat dp[x] het aantal manieren zijn om x te vormen. Begin met één manier om nul te maken: de lege verzameling munten.
dp = [0]*(A+1)
dp[0] = 1Zet de muntlus buitenom
Zet de muntlus aan de buitenkant van de bedraglus. Met deze volgorde telt elke combinatie precies één keer mee, nooit meerdere volgordes.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Combinaties versus permutaties
Wissel de volgorde van de lussen om en je telt in plaats daarvan geordende manieren. Alleen de nesting van de lussen verandert al de betekenis van het antwoord.
Variant met het minimale aantal munten
Voor het kleinste aantal munten bewaar je een minimum in plaats van een som. Initialiseer met oneindig en neem één plus het beste deelprobleem.
dp[x] = min(dp[x], dp[x-c] + 1)Eén patroon, veel vormen
Traplopen en munten hebben dezelfde vorm: elke toestand telt enkele vorige toestanden op of neemt daar het minimum van. Als je dat herkent, schrijft de code zichzelf.
Snelle controle
Bij het tellen van muntcombinaties: welke lusvolgorde voorkomt duplicaten?
Samenvatting: tel de laatste stappen op
Je kunt nu traplopen en munten tellen met een 1D-recursie. Elk antwoord telt enkele eerdere toestanden op en de lusvolgorde bepaalt combinaties versus permutaties.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Trappen beklimmen en muntcombinaties” gratis?
Ja — de volledige tekst van “Trappen beklimmen en muntcombinaties” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Trappen beklimmen en muntcombinaties”?
Klassieke 1D-recursies vanaf nul opbouwen Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Trappen beklimmen en muntcombinaties”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Memoization versus tabulation
- Toestand en transitie definiëren
- Trappen beklimmen en muntcombinaties
- Langste stijgende subsequence