Competitive Programming Academy · Oppitunti

Polkujen laskeminen ruudukossa

Laske polkujen summa kulmasta kulmaan

Oppitunti 1/413 vaihetta

Polkujen laskeminen ruudukossa on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.

Klassinen ruudukko-ongelma

Aloitatte ruudukon vasemmasta yläkulmasta ja haluatte päästä oikeaan alakulmaan. Jokainen askel siirtää oikealle tai alas. Kuinka monta erilaista polkua on olemassa?

Miksi DP sopii tähän

Jokaiseen soluun pääsee yläpuolella olevasta solusta tai vasemmalla olevasta solusta. Tämä päällekkäisyys on juuri syy siihen, miksi kyseessä on DP-ongelma.

Määritä tila

Olkoon dp[i][j] niiden tapojen määrä, joilla aloitussolusta pääsee soluun (i, j). Tilan selkeä nimeäminen on puolet työstä.

Siirtymä

Voitte saapua soluun vain ylhäältä tai vasemmalta, joten määrä on näiden summa. Tämä on siirtymä, joka ohjaa koko taulukkoa.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Kantatapaus

Aloitussoluun pääsee täsmälleen yhdellä tavalla: tekemättä mitään. Siksi dp[0][0] on 1 ennen kuin täytätte mitään muuta.

dp[0][0] = 1

Reunoilla on yksi polku

Ylärivin tai vasemman sarakkeen soluilla on yksi suora reitti. Niiden määrä on aina 1, koska toinen naapuri on ruudukon ulkopuolella.

Rakenna taulukko

Luokaa m kertaa n -taulukko, joka on täytetty nollilla. Kun koko määritetään etukäteen, indeksointi pysyy siistinä ja yllätyksiltä vältytään.

dp = [[0] * n for _ in range(m)]

Täytä lukemisjärjestyksessä

Käykää ensin rivit ja sitten sarakkeet ylhäältä alas ja vasemmalta oikealle. Tämä järjestys takaa, että molemmat naapurit on käsitelty ennen niiden käyttöä.

for i in range(m):
    for j in range(n):
        ...

Vastaussolu

Täytön jälkeen polkujen määrä on viimeisessä solussa. Vastaus on dp[m-1][n-1], eli oikean alakulman solu.

answer = dp[m-1][n-1]

Säästä muistia yhdellä rivillä

Kukin rivi tarvitsee vain yläpuolella olevan rivin, joten voitte säilyttää yhden rivin ja päivittää sitä paikallaan. Tällöin muistin tarve pienenee arvoon O(n).

row[j] += row[j-1]

Matemaattinen oikotie

Kun esteitä ei ole, vastaus on binomikerroin: valitaan, mitkä kaikista askelista kulkevat alas. DP on silti parempi, kun mukaan tulee esteitä.

Pikatarkistus

Täytätte dp[i][j]-arvoa avoimelle sisäsolulle. Mikä kaava on oikea?

Vastaa interaktiivisessa oppitunnissa

Kertaus: polkujen laskeminen

Määritelkää dp soluun johtavien polkujen määräksi, asettakaa dp[0][0] arvoksi 1 ja laskekaa yhteen yläpuolella sekä vasemmalla oleva solu. Kulmassa on vastaus. 🧭

Aloita maksutta

Opi Python tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 30
Oppitunnit: 120

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Polkujen laskeminen ruudukossa” ilmainen?

Kyllä – oppitunnin ”Polkujen laskeminen ruudukossa” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Polkujen laskeminen ruudukossa”?

Laske polkujen summa kulmasta kulmaan Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.

Kuinka kauan ”Polkujen laskeminen ruudukossa”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?

Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

← Takaisin: Competitive Programming Academy