Dynaaminen ohjelmointi on matematiikassa ja tietojenkäsittelytieteessä käytetty menetelmä monimutkaisten ongelmien ratkaisemiseksi jakamalla ne yksinkertaisempiin osaongelmiin. Ratkaisemalla jokainen aliongelma vain kerran ja tallentamalla tulokset, se välttää redundantteja laskelmia, mikä johtaa tehokkaampiin ratkaisuihin monenlaisiin ongelmiin. Tämä artikkeli tarjoaa yksityiskohtaisen tutkimuksen dynaamisista ohjelmointikonsepteista esimerkein havainnollistettuna.

java laskuri

Dynaaminen ohjelmointi

Sisällysluettelo

• Mitä on dynaaminen ohjelmointi?
• Kuinka dynaaminen ohjelmointi toimii?
• Esimerkkejä dynaamisesta ohjelmoinnista
• Milloin käyttää dynaamista ohjelmointia?
• Dynaamisen ohjelmoinnin lähestymistavat
• Dynaaminen ohjelmointialgoritmi
• Dynaamisen ohjelmoinnin edut
• Dynaamisen ohjelmoinnin sovellukset
• Opi dynaamisen ohjelmoinnin perusteet
• Dynaamisen ohjelmoinnin edistyneet käsitteet
• Dynaamiset ohjelmointiongelmat

Mikä on dynaaminen ohjelmointi (DP)?

Dynaaminen ohjelmointi (DP) on matematiikassa ja tietojenkäsittelytieteessä käytetty menetelmä monimutkaisten ongelmien ratkaisemiseksi jakamalla ne yksinkertaisempiin osaongelmiin. Ratkaisemalla jokainen aliongelma vain kerran ja tallentamalla tulokset, se välttää redundantteja laskelmia, mikä johtaa tehokkaampiin ratkaisuihin monenlaisiin ongelmiin.

Kuinka dynaaminen ohjelmointi (DP) toimii?

• Tunnista aliongelmat: Jaa pääongelma pienempiin, itsenäisiin osaongelmiin.
• Kaupan ratkaisut: Ratkaise jokainen aliongelma ja tallenna ratkaisu taulukkoon tai taulukkoon.
• Rakennusratkaisut: Käytä tallennettuja ratkaisuja rakentaaksesi ratkaisun pääongelmaan.
• Vältä redundanssia: Tallentamalla ratkaisuja DP varmistaa, että jokainen aliongelma ratkaistaan ​​vain kerran, mikä vähentää laskenta-aikaa.

Esimerkkejä dynaamisesta ohjelmoinnista (DP)

Esimerkki 1: Harkitse Fibonacci-sekvenssin löytämisen ongelmaa:

Fibonaccin sekvenssi: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Raaka voima -lähestymistapa:

Löytääksesi n:nnen Fibonacci-luvun raa'alla voimalla, lisää vain (n-1) ja (n-2) Fibonaccin numerot. Tämä toimisi, mutta se olisi tehotonta suurille arvoille n , koska se vaatisi kaikkien aiempien Fibonacci-lukujen laskemisen.

Dynaaminen ohjelmointimenetelmä:

Fibonacci-sarja, jossa käytetään dynaamista ohjelmointia

• Aliongelmat: F(0), F(1), F(2), F(3), …
• Kaupan ratkaisut: Luo taulukko tallentaaksesi F(n):n arvot, kun ne lasketaan.
• Rakennusratkaisut: Etsi F(n) taulukosta F(n-1) ja F(n-2) ja lisää ne.
• Vältä redundanssia: Taulukko varmistaa, että jokainen osaongelma (esim. F(2)) ratkaistaan ​​vain kerran.

Käyttämällä DP:tä voimme laskea Fibonacci-sekvenssin tehokkaasti ilman, että aliongelmia tarvitsee laskea uudelleen.

ymail

Esimerkki 2: Pisin yhteinen osasekvenssi (kahdelle merkkijonolle yhteisen pisimmän osasekvenssin löytäminen)

Esimerkki 3: Lyhin polku kaaviossa (lyhimmän polun löytäminen kaavion kahden solmun välillä)

Esimerkki 4: Reppuongelma (reppuun tietyn kapasiteetin omaan reppuun mahtuvien tavaroiden enimmäisarvon löytäminen)

Milloin käyttää dynaamista ohjelmointia (DP)?

Dynaaminen ohjelmointi on optimointitekniikka, jota käytetään ongelmien ratkaisemiseen ja joka koostuu seuraavista ominaisuuksista:

1. Optimaalinen alusrakenne:

Optimaalinen alirakenne tarkoittaa, että yhdistämme aliongelmien optimaaliset tulokset saavuttaaksemme suuremman ongelman optimaalisen tuloksen.

linux isäntä

Esimerkki:

Harkitse ongelmaa löytää minimikustannukset polku painotetussa kaaviossa alkaen a lähde solmu a määränpäähän solmu. Voimme jakaa tämän ongelman pienempiin osaongelmiin:

• Etsi minimi kustannus polkua lähde solmu jokaiselle keskitason solmu.
• Etsi minimi kustannus polku jokaisesta keskitason solmu määränpäähän solmu.

Ratkaisu suurempaan ongelmaan (minimikustannuspolun löytäminen lähdesolmusta kohdesolmuun) voidaan rakentaa näiden pienempien aliongelmien ratkaisuista.

2. Päällekkäiset aliongelmat:

Samat osaongelmat ratkaistaan ​​toistuvasti ongelman eri osissa.

Esimerkki:

Harkitse laskennan ongelmaa Fibonacci sarja . Fibonacci-luvun laskeminen indeksissä n , meidän on laskettava Fibonacci-luvut indekseissä n-1 ja n-2 . Tämä tarkoittaa, että Fibonacci-luvun laskemisen osaongelma indeksissä n-1 käytetään kahdesti ratkaisussa suurempaan ongelmaan, joka koskee Fibonacci-luvun laskemista indeksissä n .

Dynaamisen ohjelmoinnin lähestymistavat (DP)

Dynaaminen ohjelmointi voidaan saavuttaa käyttämällä kahta lähestymistapaa:

1. Ylhäältä alas -lähestymistapa (muistiinpano):

Ylhäältä alas -lähestymistavassa, joka tunnetaan myös nimellä muisteleminen , aloitamme lopullisesta ratkaisusta ja jaamme sen rekursiivisesti pienempiin osaongelmiin. Ylimääräisten laskelmien välttämiseksi tallennamme ratkaistujen aliongelmien tulokset muistitaulukkoon.

Tarkastellaan ylhäältä alas -lähestymistapaa:

• Aloittaa lopullisesta ratkaisusta ja jakaa sen rekursiivisesti pienempiin osaongelmiin.
• Tallentaa osaongelmien ratkaisut taulukkoon tarpeettomien laskelmien välttämiseksi.
• Soveltuu, kun osaongelmien määrä on suuri ja monia niistä käytetään uudelleen.

2. Alhaalta ylös -lähestymistapa (taulukko):

Alhaalta ylös -lähestymistavassa, joka tunnetaan myös nimellä taulukointi , aloitamme pienimmistä osaongelmista ja rakennamme vähitellen lopulliseen ratkaisuun. Tallennamme ratkaistujen osaongelmien tulokset taulukkoon tarpeettomien laskelmien välttämiseksi.

Tarkastellaan alhaalta ylös -lähestymistapaa:

• Aloittaa pienimmistä osaongelmista ja kasvaa vähitellen lopulliseen ratkaisuun.
• Täyttää taulukon aliongelmien ratkaisuilla alhaalta ylöspäin.
• Soveltuu, kun osaongelmien määrä on pieni ja optimaalinen ratkaisu voidaan laskea suoraan ratkaisuista pienempiin osaongelmiin.

Dynaaminen ohjelmointi (DP) Algoritmi

Dynaaminen ohjelmointi on algoritminen tekniikka, joka ratkaisee monimutkaisia ​​ongelmia jakamalla ne pienempiin osaongelmiin ja tallentamalla niiden ratkaisut tulevaa käyttöä varten. Se on erityisen tehokas ongelmiin, jotka sisältävät päällekkäisiä aliongelmia ja optimaalinen alusrakenne.

muuntaa merkkijono json-objektiksi

Yleiset dynaamista ohjelmointia käyttävät algoritmit:

• Pisin yhteinen jakso (LCS): Löytää pisimmän yhteisen osajonon kahden merkkijonon välillä.
• Lyhin reitti kaaviossa: Löytää lyhimmän polun kaavion kahden solmun välillä.
• Reppuongelma: Määrittää niiden esineiden enimmäisarvon, jotka voidaan sijoittaa tietyn kapasiteetin omaavaan reppuun.
• Matriisiketjun kertolasku: Optimoi matriisin kertolaskujärjestyksen operaatioiden määrän minimoimiseksi.
• Fibonacci-sekvenssi: Laskee n:nnen Fibonacci-luvun.

Dynaamisen ohjelmoinnin edut (DP)

Dynaamisella ohjelmoinnilla on monia etuja, mukaan lukien:

• Välttää samojen aliongelmien uudelleenlaskemisen useita kertoja, mikä säästää merkittävästi aikaa.
• Varmistaa, että optimaalinen ratkaisu löydetään harkiten kaikkia mahdollisia yhdistelmiä.
• Jakaa monimutkaiset ongelmat pienempiin, paremmin hallittavissa oleviin aliongelmiin.

Dynaamisen ohjelmoinnin sovellukset (DP)

Dynaamisella ohjelmoinnilla on laaja valikoima sovelluksia, mukaan lukien:

• Optimointi: Reppu-ongelma, lyhimmän polun ongelma, suurimman alijärjestelmän ongelma
• Tietokone Tiede: Pisin yhteinen osasekvenssi, muokkausetäisyys, merkkijonojen sovitus
• Toimintatutkimus: Varastonhallinta, aikataulutus, resurssien allokointi

Tutustutaan nyt kattavaan etenemissuunnitelmaan dynaamisen ohjelmoinnin hallitsemiseksi.

Opi dynaamisen ohjelmoinnin perusteet (DP)

• Mitä memoisointi on? Täydellinen opetusohjelma
• Taulukko vs memoisaatio
• Optimaalinen alustan ominaisuus
• Päällekkäiset aliongelmat -ominaisuus
• Kuinka ratkaista dynaamisen ohjelmoinnin ongelma?

• Fibonaccin numerot
• n. katalaaninumero
• Kellon numerot (tapoja osioida joukko)
• Binomiaalinen kerroin
• Kolikon vaihtoongelma
• Osajoukon summaongelma
• Laske nCr % p
• Tangon leikkaaminen
• Aidan maalausalgoritmi
• Pisin yhteinen jakso
• Pisin kasvava jakso
• Pisin osajono siten, että vierekkäisten välinen ero on yksi
• Maksimikokoinen neliömatriisi, jossa kaikki 1:t
• Pienin kustannuspolku
• Vähimmäismäärä hyppyjä päästäksesi päähän
• Pisin yhteinen osamerkkijono (avaruuteen optimoitu DP-ratkaisu)
• Laske tavat päästä n:nnelle portaalle vaiheiden 1, 2 tai 3 avulla
• Laske kaikki mahdolliset polut mXn-matriisin vasemmasta yläkulmasta oikeaan alakulmaan
• Ainutlaatuisia polkuja esteitä sisältävässä ruudukossa

2. Keskikokoiset dynaamisen ohjelmoinnin (DP) ongelmat

• Floyd Warshall -algoritmi
• Bellman-Ford-algoritmi
• 0-1 Reppuongelma
• Tulostustarvikkeet 0/1-reppuissa
• Rajoittamaton reppu (esineiden toisto sallittu)
• Munan pudottaminen palapeli
• Word Break ongelma
• Vertex-kannen ongelma
• Laattojen pinoamisongelma
• Laatikon pinoamisongelma
• Osioongelma
• Travelling Salesman Problem | Sarja 1 (naiivi ja dynaaminen ohjelmointi)
• Pisin palindrominen alajakso
• Pisin yleinen lisääntyvä osajakso (LCS + LIS)
• Etsi taulukon kaikki erilliset osajoukon (tai osajonon) summat
• Painotettu työaikataulu
• Laske poikkeamat (permutaatio siten, että mikään elementti ei näy alkuperäisessä paikassaan)
• Minimi lisäys palindromin muodostamiseksi
• Jokerimerkkikuvion vastaavuus
• Tapoja järjestää pallot siten, että vierekkäiset pallot ovat erityyppisiä

3. Vaikeita ongelmia dynaamisessa ohjelmoinnissa (DP)

• Palindromin osiointi
• Sanojen rivitys-ongelma
• Maalarin osioongelma
• Ohjelma Bridge and Torch -ongelmaan
• Matriisiketjun kertolasku
• Hakasulkeiden tulostaminen matriisiketjun kertolaskuongelmassa
• Maksimisummasuorakulmio 2D-matriisissa
• Suurin voitto ostamalla ja myymällä osaketta enintään k kertaa
• Minimikustannus merkkijonojen lajittelusta eri kustannusten käänteisoperaatioilla
• AP (aritmeettinen progressio) osasekvenssien määrä taulukossa
• Johdatus dynaamiseen ohjelmointiin puilla
• Puun enimmäiskorkeus, kun mitä tahansa solmua voidaan pitää juurina
• Pisin toistuva ja ei-päällekkäinen osamerkkijono

Pikalinkit:

• Opi tietorakenne ja algoritmit | DSA opetusohjelma
• 20 parasta dynaamisen ohjelmoinnin haastattelukysymystä
• 'Harjoitteluongelmat' dynaamisessa ohjelmoinnissa
• Dynaamisen ohjelmoinnin tietokilpailu