Trappor och myntkombinationer
Klassiska endimensionella rekurrenser från grunden
Trappor och myntkombinationer är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Introduktion till trappstegsproblemet
Du kan ta 1 eller 2 steg åt gången. Hur många sätt finns det att nå steg n? Den klassiska 1D-DP:n är egentligen Fibonacci i förklädnad.
Hitta rekurrensen
För att stå på steg i kom du från i-1 eller i-2. Alltså är dp[i] = dp[i-1] + dp[i-2], där de två senaste stegen summeras.
dp[i] = dp[i-1] + dp[i-2]Ange basfallen
Det finns ett sätt att stå kvar på marken och ett sätt att nå steg 1. Dessa basfall initierar hela tabellen.
dp[0], dp[1] = 1, 1Fyll i och läs av svaret
Iterera uppåt, så innehåller den sista cellen antalet sätt. Hela lösningen är en liten loop för tabulering.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Minska till två variabler
Du behöver bara de två senaste värdena, så ta bort arrayen. Den här versionen med O(1)-minne är tävlingsprogrammerarnas favorit.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bByt till myntkombinationer
Givet myntvärden ska du räkna antalet sätt att bilda belopp A. Ordningen spelar ingen roll här, så vi räknar kombinationer, inte sekvenser.
coins = [1, 2, 5]Kombinationstabellen
Låt dp[x] vara antalet sätt att bilda x. Börja med ett sätt att bilda noll: den tomma mängden mynt.
dp = [0]*(A+1)
dp[0] = 1Lägg myntloopen ytterst
Placera myntloopen ytterst och beloppsloopen innerst. Den här ordningen räknar varje kombination exakt en gång, aldrig permutationer.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Kombinationer kontra permutationer
Byt loopordning, så räknar du i stället ordnade sätt. Enbart looparnas nästling ändrar vad svaret betyder.
Variant: minsta antal mynt
För att hitta det minsta antalet mynt sparar du ett minimum i stället för en summa. Initiera med oändlighet och ta 1 plus det bästa delproblemet.
dp[x] = min(dp[x], dp[x-c] + 1)Ett mönster, många uttryck
Trappsteg och mynt har samma struktur: varje tillstånd summerar eller minimerar över några tidigare tillstånd. När du ser det skriver koden nästan sig själv.
Snabb kontroll
När du räknar myntkombinationer, vilken loopordning undviker dubbletter?
Sammanfattning: Summera de senaste stegen
Du kan nu lösa trappstegsproblemet och myntproblemet med en 1D-rekurrens. Varje svar summerar några tidigare tillstånd, och loopordningen avgör kombinationer kontra permutationer.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Trappor och myntkombinationer” gratis?
Ja – hela texten till ”Trappor och myntkombinationer” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Trappor och myntkombinationer”?
Klassiska endimensionella rekurrenser från grunden Ni övar på Competitive Programming Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Trappor och myntkombinationer”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Memoisering kontra tabulering
- Definiera tillstånd och övergång
- Trappor och myntkombinationer
- Längsta växande delsekvens