Trappegang og myntkombinasjoner
Klassiske endimensjonale rekurrenser fra grunnen av
Trappegang og myntkombinasjoner er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Bli kjent med trappeproblemet
Du kan ta 1 eller 2 trinn om gangen. Hvor mange måter finnes det å nå trinn n på? Denne klassiske 1D-DP-en er egentlig Fibonacci i forkledning.
Finn rekursjonen
For å stå på trinn i kom du fra i-1 eller i-2. Derfor er dp[i] = dp[i-1] + dp[i-2], siden vi summerer de to siste stegene.
dp[i] = dp[i-1] + dp[i-2]Angi basistilfellene
Det finnes én måte å bli stående på bakken på, og én måte å nå trinn 1 på. Disse basistilfellene danner grunnlaget for hele tabellen.
dp[0], dp[1] = 1, 1Fyll ut og les av svaret
Gå oppover i tabellen, så inneholder den siste cellen antallet. Hele løsningen er en liten løkke med tabulering.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Reduser til to variabler
Du trenger bare de to siste verdiene, så du kan fjerne arrayet. Denne versjonen med O(1)-plass er en favoritt i konkurranser.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bBytt til myntkombinasjoner
Med gitte myntverdier skal du telle antall måter å lage beløpet A på. Rekkefølgen spiller ingen rolle her, så vi teller kombinasjoner, ikke sekvenser.
coins = [1, 2, 5]Kombinasjonstabellen
La dp[x] være antallet måter å lage x på. Start med én måte å lage null på: den tomme mengden mynter.
dp = [0]*(A+1)
dp[0] = 1La myntløkken komme ytterst
Plasser myntløkken ytterst, utenfor løkken over beløp. Denne rekkefølgen teller hver kombinasjon nøyaktig én gang, aldri permutasjoner.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Kombinasjoner kontra permutasjoner
Bytter du rekkefølgen på løkkene, teller du i stedet ordnede måter. Bare løkkenes nøsting endrer betydningen av svaret.
Variant av myntveksling med minimum
For færrest mulig mynter lagrer du et minimum i stedet for en sum. Initialiser med uendelig, og ta 1 pluss det beste delproblemet.
dp[x] = min(dp[x], dp[x-c] + 1)Ett mønster, mange varianter
Trapper og mynter har samme form: hver tilstand summerer eller minimerer over noen få tidligere tilstander. Når du ser dette, skriver koden seg nesten selv.
Rask sjekk
Når du teller myntkombinasjoner, hvilken løkkerekkefølge unngår duplikater?
Oppsummering: Summer de siste stegene
Du kan nå løse trappeproblemet og mynttelling med en 1D-rekursjon. Hvert svar summerer noen tidligere tilstander, og løkkerekkefølgen avgjør kombinasjoner kontra permutasjoner.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Trappegang og myntkombinasjoner» gratis?
Ja – hele teksten i «Trappegang og myntkombinasjoner» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Trappegang og myntkombinasjoner»?
Klassiske endimensjonale rekurrenser fra grunnen av Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Trappegang og myntkombinasjoner»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Memoisering mot tabulering
- Definer tilstand og overgang
- Trappegang og myntkombinasjoner
- Lengste økende delsekvens