Definiera tillstånd och övergång
Ange exakt vad dp[i] betyder
Definiera tillstånd och övergång är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 2 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.
DP:s kärna
Varje DP börjar med att definiera ett tillstånd: Vad representerar dp[i] egentligen? När denna mening är korrekt faller resten på plats.
Tillståndet måste vara exakt
Skriv betydelsen med ord: dp[i] = svaret för de första i elementen. En otydlig tillståndsdefinition leder till en felaktig rekurrens.
dp[i] = best total using items 0..i-1Övergången
Övergången beskriver hur dp[i] byggs upp från tidigare tillstånd. Det är rekurrensformeln i lösningens kärna.
dp[i] = dp[i-1] + dp[i-2]Basfallen förankrar lösningen
Basfall är de minsta tillstånden som Ni känner till direkt. Utan korrekta grundvärden blir alla senare värden fel.
dp[0] = 1Välj en beräkningsordning
Varje tillstånd måste fyllas i efter de tillstånd som det beror på. Den beroenderegeln avgör loopens riktning.
for i in range(1, n+1): ...Var finns svaret
Bestäm vilken cell som innehåller slutresultatet. Ofta är det dp[n], men ibland är det maximum över hela tabellen.
answer = dp[n] # or max(dp)Räkna tillstånden
Antalet distinkta tillstånd avgör Er tidsbudget. En endimensionell dp över n element har O(n) tillstånd att fylla i.
Kostnad per övergång
Den totala tiden är antalet tillstånd multiplicerat med arbetet per övergång. En övergång på O(n) inuti n tillstånd ger O(n i kvadrat).
Lägg till en dimension vid behov
Om ett index inte räcker för att beskriva situationen lägger Ni till ett till. En andra dimension förvandlar dp[i] till dp[i][j].
dp = [[0]*(c+1) for _ in range(n+1)]Återskapa valet
För att återskapa den faktiska lösningen sparar du vilken övergång som vann i varje tillstånd och går sedan bakåt från svaret.
choice[i] = "take"En återanvändbar checklista
Tillstånd, övergång, basfall, ordning, svar. Fastställ dessa fem, så faller nästan vilken DP-rekurrens som helst på plats.
Snabb kontroll
Du utformar en DP-lösning. Vad representerar dp[i]?
Sammanfattning: Namnge det och lös det sedan
Du kan nu definiera ett tillstånd, skriva dess övergång, ange basfall och hitta svaret. Den ritningen förvandlar DP från gissningsarbete till en metod.
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 ”Definiera tillstånd och övergång” gratis?
Ja – hela texten till ”Definiera tillstånd och övergång” 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 ”Definiera tillstånd och övergång”?
Ange exakt vad dp[i] betyder 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 2 av 4.
Hur lång tid tar lektionen ”Definiera tillstånd och övergång”?
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