Pisin yhteinen alijono
Kohdista kaksi merkkijonoa DP-taulukon avulla
Pisin yhteinen alijono on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.
Mikä alijono on
Alijono säilyttää merkkien järjestyksen, mutta joitakin merkkejä voi jättää väliin. Merkkijonosta 'abcde' voi poimia 'ace', mutta ei koskaan 'aec'.
LCS:n tavoite
Kahdesta merkkijonosta pisin yhteinen alijono on pisin jono, joka esiintyy molemmissa samassa suhteellisessa järjestyksessä.
Siirry ruudukkoon
Vertailkaa merkkijonojen etuliitteitä. Niiden pituuksien perusteella muodostettu kaksiulotteinen taulukko muuttaa tämän tutuksi ruudukko-DP:ksi.
Määritä tila
Olkoon dp[i][j] A:n ensimmäisten i merkin ja B:n ensimmäisten j merkin LCS:n pituus.
Kun merkit täsmäävät
Jos A[i-1] on yhtä suuri kuin B[j-1], yhteinen merkki pidentää LCS:ää. Lisäätte yhden diagonaaliarvoon dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Kun merkit eroavat
Jos merkit eroavat, jättäkää toinen merkki jommastakummasta merkkijonosta pois ja säilyttäkää parempi tulos. Valitsette kahden naapurin max-arvon.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Kantatapaus
Tyhjä etuliite ei jaa mitään, joten LCS:n pituus on nolla. Rivi 0 ja sarake 0 sisältävät pelkkiä nollia.
dp = [[0] * (m+1) for _ in range(n+1)]Yksi ylimääräinen rivi ja sarake
Kun taulukon kooksi asetetaan n+1 kertaa m+1, saatte tyhjän nolla-arvoisen reunan. Näin reunojen hankalilta rajoitustarkistuksilta vältytään.
Täytä taulukko
Käykää i ja j läpi alkaen arvosta 1. Kukin solu tarvitsee vain yläpuolella, vasemmalla ja diagonaalissa olevat arvot, jotka on jo laskettu.
for i in range(1, n+1):
for j in range(1, m+1):
...Lue pituus
Koko LCS:n pituus on kulmassa. Vastaus on dp[n][m], kun kaikki solut on täytetty.
length = dp[n][m]Aikavaativuus
Käsittelette jokaisen solun kerran, joten aika- ja muistitilavuus ovat O(n times m). Tämä riittää hyvin muutaman tuhannen merkin pituisille merkkijonoille.
Pikatarkistus
Nykyiset merkit A[i-1] ja B[j-1] ovat samat. Mikä päivitys on oikein?
Kertaus: LCS
Rakentakaa n+1 kertaa m+1 -taulukko: täsmäyksessä lisätkää yksi diagonaaliin, muuten valitkaa suurin naapuri. Kulmassa on pituus. 🔗
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
Usein kysytyt kysymykset
Onko oppitunti ”Pisin yhteinen alijono” ilmainen?
Kyllä – oppitunnin ”Pisin yhteinen alijono” 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 ”Pisin yhteinen alijono”?
Kohdista kaksi merkkijonoa DP-taulukon avulla 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 3/4.
Kuinka kauan ”Pisin yhteinen alijono”-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
- Polkujen laskeminen ruudukossa
- Pienin polkusumma esteiden kanssa
- Pisin yhteinen alijono
- Editointietäisyys vaihe vaiheelta