Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Pienin polkusumma esteiden kanssa

Pidä pienin kustannus mukana solusta toiseen

Oppitunti 2/413 vaihetta

Pienin polkusumma esteiden kanssa on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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 Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Laskennasta kustannuksiin

Nyt jokaisella solulla on arvo, ja haluatte löytää halvimman reitin kulmaan. Tavoite vaihtuu polkujen laskemisesta kustannuksen minimointiin.

Määritä tila

Olkoon dp[i][j] pienin kokonaiskustannus, jolla soluun (i, j) pääsee. Ruudukko ja siirtymät ovat samat, mutta nyt seuraamme summien emmekä määrien laskemista.

Siirtymä

Valitsette kahdesta saapuvasta naapurista halvemman ja lisäätte nykyisen solun arvon. Tämä min-valinta on rekursion ydin.

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Merkitse esteet

Este on solu, jolle ei voi astua. Antakaa sille äärettömän suuri kustannus, jotta mikään sen kautta kulkeva polku ei voi olla pienin.

INF = float('inf')

Käsittele esto selkeästi

Kun ruudukko merkitsee solun estetetyksi, asettakaa sen dp arvoksi ääretön ja jatkakaa eteenpäin. min-vaihe välttää sen luonnostaan.

if blocked(i, j):
    dp[i][j] = INF
    continue

Varmista aloitus

Jos aloitussolu on estetty, mitään polkua ei ole. Tarkistakaa tämä ensin, jotta ette palauta virheellistä kustannusta.

Alusta ensimmäinen solu

Aloitussolulla ei ole naapureita, joista siihen voisi saapua, joten sen kustannus on vain sen oma arvo. Asettakaa dp[0][0] ennen silmukoiden suorittamista.

dp[0][0] = grid[0][0]

Käsittele reunat

Ylärivin arvot tulevat vain vasemmalta ja vasemman sarakkeen arvot vain ylhäältä. Käsitelkää nämä reunat, jotta ette lue ruudukon ulkopuolelta.

Ääretön leviää

Äärettömän luvun lisääminen tuottaa edelleen äärettömän, joten kokonaan suljettu solu säilyttää kustannuksen INF. Saavuttamattomat solut ilmaisevat tilansa automaattisesti.

Lue tulos

Vähimmäiskustannus on oikean alakulman solussa. Jos arvo on edelleen ääretön, kelvollista polkua ei ole.

ans = dp[m-1][n-1]
if ans == INF:
    ans = -1

Milloin ahneus epäonnistuu

Aina pienemmän naapurin suuntaan eteneminen voi johtaa umpikujaan. Vain täysi DP takaa maailmanlaajuisesti halvimman polun, ei ahne vilkaisu.

Pikatarkistus

Miten saatte polkujen DP:n välttämään estetyn solun ilman, että jokainen naapuri käsitellään erikseen?

Vastaa interaktiivisessa oppitunnissa

Kertaus: pienin polku esteiden kanssa

Valitkaa halvempi naapuri, lisätkää solun arvo, asettakaa estetyt solut äärettömiksi ja lukekaa kulman arvo. INF kulmassa tarkoittaa, ettei polkua ole. 🧱

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin 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: 90
Oppitunnit: 360

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Pienin polkusumma esteiden kanssa” ilmainen?

Kyllä – oppitunnin ”Pienin polkusumma esteiden kanssa” 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 Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Pienin polkusumma esteiden kanssa”?

Pidä pienin kustannus mukana solusta toiseen Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

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

Kuinka kauan ”Pienin polkusumma esteiden kanssa”-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ä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-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: Valmistautuminen ohjelmointihaastatteluihin