Definer tilstand og overgang
Angi nøyaktig hva dp[i] betyr
Definer tilstand og overgang er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 2 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 Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hjertet i DP
All DP starter med å navngi en tilstand: Hva representerer dp[i] egentlig? Får du denne setningen riktig, følger resten.
Tilstanden må være presis
Skriv betydningen med ord: dp[i] = svaret for de første i elementene. En uklar tilstandsdefinisjon fører til en feilaktig rekurrens.
dp[i] = best total using items 0..i-1Overgangen
Overgangen forklarer hvordan dp[i] bygges fra tidligere tilstander. Det er rekurrensligningen som står sentralt i løsningen.
dp[i] = dp[i-1] + dp[i-2]Grunntilfellene forankrer løsningen
Grunntilfeller er de minste tilstandene du kjenner direkte. Uten korrekte forankringer blir alle senere verdier feil.
dp[0] = 1Velg en beregningsrekkefølge
Hver tilstand må fylles ut etter tilstandene den avhenger av. Denne avhengighetsregelen bestemmer retningen på løkken.
for i in range(1, n+1): ...Hvor ligger svaret
Bestem hvilken celle som inneholder det endelige resultatet. Ofte er det dp[n], men noen ganger er det maksimumet i hele tabellen.
answer = dp[n] # or max(dp)Tell tilstandene
Antallet forskjellige tilstander bestemmer tidsbudsjettet. En 1D-dp over n elementer har O(n) tilstander som må fylles ut.
Kostnad per overgang
Den totale tiden er antall tilstander multiplisert med arbeidet per overgang. En O(n)-overgang i n tilstander gir O(n²).
Legg til en dimensjon ved behov
Hvis én indeks ikke kan beskrive situasjonen, legger du til en til. En ekstra dimensjon gjør dp[i] om til dp[i][j].
dp = [[0]*(c+1) for _ in range(n+1)]Gjenskap valget
For å finne den faktiske løsningen lagrer du hvilken overgang som vant i hver tilstand, og går deretter bakover fra svaret.
choice[i] = "take"En sjekkliste du kan bruke igjen
Tilstand, overgang, basistilfelle, rekkefølge, svar. Fastslå disse fem, så faller nesten enhver DP-rekursjon på plass.
Rask sjekk
Du utformer en DP. Hva representerer dp[i]?
Oppsummering: Gi den et navn, og løs den
Du kan nå definere en tilstand, skrive overgangen, angi basistilfeller og finne svaret. Denne oppskriften gjør DP om fra gjetting til en fast fremgangsmåte.
Lær deg Python 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
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Definer tilstand og overgang» gratis?
Ja – hele teksten i «Definer tilstand og overgang» 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 Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Definer tilstand og overgang»?
Angi nøyaktig hva dp[i] betyr Du øver på Competitive Programming Academy 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 Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy 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 2 av 4.
Hvor lang tid tar leksjonen «Definer tilstand og overgang»?
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 Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-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