Tell stier i et rutenett
Summer stier fra hjørne til hjørne
Tell stier i et rutenett er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 1 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.
Det klassiske rutenettproblemet
Du starter øverst til venstre i et rutenett og vil til nederst til høyre. Hvert steg går mot høyre eller nedover. Hvor mange ulike stier finnes?
Hvorfor DP passer
Hver celle kan nås fra cellen over eller cellen til venstre. Dette overlappet er nettopp grunnen til at dette er et DP-problem.
Definer tilstanden
La dp[i][j] være antallet måter å nå celle (i, j) på fra startpunktet. Å navngi tilstanden tydelig er halve jobben.
Overgangen
Du kommer bare fra ovenfra eller fra venstre, så antallet er summen av disse. Dette er overgangen som driver hele tabellen.
dp[i][j] = dp[i-1][j] + dp[i][j-1]Grunntilfellet
Startcellen kan nås på nøyaktig én måte: ved å ikke gjøre noe. Derfor er dp[0][0] lik 1 før Du fyller ut resten.
dp[0][0] = 1Kantene har én sti
Celler i øverste rad eller venstre kolonne har én rett rute. Antallet deres er alltid 1, siden én nabo ligger utenfor rutenettet.
Bygg tabellen
Lag en m ganger n-tabell fylt med nuller. Når størrelsen bestemmes på forhånd, blir indekseringen ryddig, og Du unngår overraskelser.
dp = [[0] * n for _ in range(m)]Fyll ut i leserekkefølge
Gå gjennom rader og deretter kolonner, ovenfra og ned og fra venstre mot høyre. Denne rekkefølgen sikrer at begge naboene er klare før Du bruker dem.
for i in range(m):
for j in range(n):
...Svarcellen
Etter utfyllingen ligger antallet stier i den siste cellen. Svaret er dp[m-1][n-1], altså hjørnet nederst til høyre.
answer = dp[m-1][n-1]Spar minne med én rad
Hver rad trenger bare raden over, så Du kan beholde én enkelt rad og oppdatere den på stedet. Det reduserer minnebruken til O(n).
row[j] += row[j-1]Den matematiske snarveien
Uten blokker er svaret en binomialkoeffisient: velg hvilke av de totale stegene som skal gå nedover. DP er likevel best når hindringer dukker opp.
Hurtigsjekk
Du fyller ut dp[i][j] for en åpen indre celle. Hvilken formel er riktig?
Oppsummering: Stitelling
Definer dp som antallet stier til en celle, sett dp[0][0] til 1, og legg sammen cellen over og cellen til venstre. Hjørnet inneholder svaret. 🧭
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 «Tell stier i et rutenett» gratis?
Ja – hele teksten i «Tell stier i et rutenett» 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 «Tell stier i et rutenett»?
Summer stier fra hjørne til hjørne 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 1 av 4.
Hvor lang tid tar leksjonen «Tell stier i et rutenett»?
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
- Tell stier i et rutenett
- Minste stisum med hindringer
- Lengste felles delsekvens
- Redigeringsavstand steg for steg