Tilan ja siirtymän määrittäminen
Määritä täsmällisesti, mitä dp[i] tarkoittaa
Tilan ja siirtymän määrittäminen 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.
DP:n ydin
Jokainen DP-ratkaisu alkaa tilan määrittelemisestä: mitä dp[i] oikeastaan tarkoittaa? Kun tämä virke on oikein, loppu seuraa sen pohjalta.
Tilan on oltava täsmällinen
Kirjoittakaa merkitys sanoin: dp[i] = ensimmäisten i alkion vastaus. Epämääräinen tilan määritelmä johtaa virheelliseen palautuskaavaan.
dp[i] = best total using items 0..i-1Siirtymä
Siirtymä kertoo, miten dp[i] muodostetaan aiemmista tiloista. Se on ratkaisun ytimessä oleva palautusyhtälö.
dp[i] = dp[i-1] + dp[i-2]Perustapaukset ankkuroivat ratkaisun
Perustapaukset ovat pienimmät tilat, joiden arvon tiedätte suoraan. Ilman oikeita ankkureita kaikki myöhemmät arvot menevät väärään suuntaan.
dp[0] = 1Valitkaa laskemisjärjestys
Jokainen tila täytyy täyttää sen jälkeen, kun siitä riippuvat tilat on täytetty. Tämä riippuvuussääntö määrää silmukan suunnan.
for i in range(1, n+1): ...Missä vastaus on
Päättäkää, mikä solu sisältää lopullisen tuloksen. Usein se on dp[n], mutta joskus vastaus on koko taulukon suurin arvo.
answer = dp[n] # or max(dp)Laskekaa tilat
Erilaisten tilojen määrä määrittää aikabudjetin. Yksiulotteisessa dp:ssä, joka käsittelee n alkiota, täytettäviä tiloja on O(n).
Siirtymän kustannus
Kokonaisaika on tilojen määrä kerrottuna yhden siirtymän työmäärällä. Jos siirtymä vie ajan O(n) ja tiloja on n, kokonaisaika on O(n squared).
Lisätkää ulottuvuus tarvittaessa
Jos yksi indeksi ei riitä kuvaamaan tilannetta, lisätkää toinen. Toinen ulottuvuus muuttaa dp[i]-muodon muotoon dp[i][j].
dp = [[0]*(c+1) for _ in range(n+1)]Palauttakaa valinta
Palauttaaksenne varsinaisen ratkaisun tallentakaa kussakin tilassa voittanut siirtymä ja kulkekaa sitten vastauksesta taaksepäin.
choice[i] = "take"Uudelleenkäytettävä tarkistuslista
Tila, siirtymä, perustapaus, järjestys ja vastaus. Kun määritätte nämä viisi, lähes jokainen DP-rekurenssi asettuu paikalleen.
Pikatarkistus
Suunnittelette DP-ratkaisua. Mitä dp[i] edustaa?
Kertaus: nimetkää se ja ratkaiskaa sitten
Osaatte nyt määritellä tilan, kirjoittaa sen siirtymän, asettaa perustapaukset ja paikantaa vastauksen. Tämä suunnitelma muuttaa DP:n arvailusta ohjeeksi.
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
Usein kysytyt kysymykset
Onko oppitunti ”Tilan ja siirtymän määrittäminen” ilmainen?
Kyllä – oppitunnin ”Tilan ja siirtymän määrittäminen” 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 ”Tilan ja siirtymän määrittäminen”?
Määritä täsmällisesti, mitä dp[i] tarkoittaa 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 ”Tilan ja siirtymän määrittäminen”-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
- Memoisointi vastaan taulukointi
- Tilan ja siirtymän määrittäminen
- Portaiden kiipeäminen ja kolikkokombinaatiot
- Pisin kasvava alijono