Dinamično programiranje je metoda, ki se uporablja v matematiki in računalništvu za reševanje zapletenih problemov z njihovo razdelitvijo na enostavnejše podprobleme. Z enkratnim reševanjem vsakega podproblema in shranjevanjem rezultatov se izogne ​​odvečnim izračunom, kar vodi do učinkovitejših rešitev za širok nabor problemov. Ta članek nudi podrobno raziskovanje konceptov dinamičnega programiranja, ponazorjeno s primeri.

java ima naslednje

Dinamično programiranje

Kazalo

• Kaj je dinamično programiranje?
• Kako deluje dinamično programiranje?
• Primeri dinamičnega programiranja
• Kdaj uporabiti dinamično programiranje?
• Pristopi dinamičnega programiranja
• Algoritem dinamičnega programiranja
• Prednosti dinamičnega programiranja
• Aplikacije dinamičnega programiranja
• Naučite se osnov dinamičnega programiranja
• Napredni koncepti v dinamičnem programiranju
• Težave z dinamičnim programiranjem

Kaj je dinamično programiranje (DP)?

Dinamično programiranje (DP) je metoda, ki se uporablja v matematiki in računalništvu za reševanje zapletenih problemov z njihovo razdelitvijo na enostavnejše podprobleme. Z enkratnim reševanjem vsakega podproblema in shranjevanjem rezultatov se izogne ​​odvečnim izračunom, kar vodi do učinkovitejših rešitev za širok nabor problemov.

Kako deluje dinamično programiranje (DP)?

• Ugotovite podprobleme: Glavni problem razdelite na manjše, samostojne podprobleme.
• Rešitve trgovine: Rešite vsak podproblem in shranite rešitev v tabelo ali polje.
• Rešitve za gradnjo: Uporabite shranjene rešitve za izgradnjo rešitve za glavni problem.
• Izogibajte se odvečnosti: S shranjevanjem rešitev DP zagotavlja, da je vsak podproblem rešen samo enkrat, kar zmanjša čas izračuna.

Primeri dinamičnega programiranja (DP)

Primer 1: Razmislite o problemu iskanja Fibonaccijevega zaporedja:

Fibonaccijevo zaporedje: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Pristop surove sile:

Če želite poiskati n-to Fibonaccijevo število s pristopom surove sile, preprosto dodajte (n-1)th in (n-2)th Fibonaccijeva števila. To bi delovalo, vendar bi bilo neučinkovito za velike vrednosti n , saj bi zahteval izračun vseh prejšnjih Fibonaccijevih števil.

Pristop dinamičnega programiranja:

Fibonaccijeva serija z uporabo dinamičnega programiranja

• podproblemi: F(0), F(1), F(2), F(3), …
• Rešitve trgovine: Ustvarite tabelo za shranjevanje vrednosti F(n), ko so izračunane.
• Rešitve za gradnjo: Za F(n) poiščite F(n-1) in F(n-2) v tabeli in ju dodajte.
• Izogibajte se odvečnosti: Tabela zagotavlja, da je vsak podproblem (npr. F(2)) rešen samo enkrat.

Z uporabo DP lahko učinkovito izračunamo Fibonaccijevo zaporedje, ne da bi morali ponovno izračunati podprobleme.

starost kylie jenner

Primer 2: Najdaljše skupno podzaporedje (iskanje najdaljšega podzaporedja, ki je skupno dvema nizoma)

Primer 3: Najkrajša pot v grafu (iskanje najkrajše poti med dvema vozliščema v grafu)

Primer 4: Problem nahrbtnika (iskanje največje vrednosti predmetov, ki jih je mogoče dati v nahrbtnik z dano kapaciteto)

Kdaj uporabiti dinamično programiranje (DP)?

Dinamično programiranje je tehnika optimizacije, ki se uporablja pri reševanju problemov in ima naslednje značilnosti:

1. Optimalna podkonstrukcija:

Optimalna podstruktura pomeni, da združimo optimalne rezultate podproblemov, da dosežemo optimalen rezultat večjega problema.

tcp in ip model

primer:

Razmislite o problemu iskanja minimalni stroški pot v uteženem grafu od a vir vozlišče do a cilj vozlišče. Ta problem lahko razdelimo na manjše podprobleme:

• Poišči najmanj stroški pot od vir vozlišče za vsako vmesni vozlišče.
• Poišči najmanj stroški pot od vsakega vmesni vozlišče za cilj vozlišče.

Rešitev večjega problema (iskanje poti z minimalnimi stroški od izvornega vozlišča do ciljnega vozlišča) je mogoče sestaviti iz rešitev teh manjših podproblemov.

2. Prekrivajoči se podproblemi:

Isti podproblemi se rešujejo večkrat v različnih delih problema.

primer:

Razmislite o problemu računanja Fibonaccijeva serija . Za izračun Fibonaccijevega števila pri indeksu n , moramo izračunati Fibonaccijeva števila z indeksi n-1 in n-2 . To pomeni, da je podproblem izračuna Fibonaccijevega števila pri indeksu n-1 se dvakrat uporabi pri rešitvi večjega problema izračuna Fibonaccijevega števila pri indeksu n .

Pristopi dinamičnega programiranja (DP)

Dinamično programiranje je mogoče doseči z uporabo dveh pristopov:

1. Pristop od zgoraj navzdol (memoizacija):

Pri pristopu od zgoraj navzdol, znanem tudi kot memoizacija , začnemo s končno rešitvijo in jo rekurzivno razdelimo na manjše podprobleme. Da se izognemo odvečnim izračunom, rezultate rešenih podproblemov shranimo v memoizacijsko tabelo.

Razčlenimo pristop od zgoraj navzdol:

• Začne se s končno rešitvijo in jo rekurzivno razdeli na manjše podprobleme.
• Rešitve podproblemov shrani v tabelo, da se izogne ​​odvečnim izračunom.
• Primerno, kadar je število podproblemov veliko in se jih veliko ponovno uporabi.

2. Pristop od spodaj navzgor (razpredelnica):

Pri pristopu od spodaj navzgor, znanem tudi kot tabeliranje , začnemo z najmanjšimi podproblemi in postopoma gradimo do končne rešitve. Rezultate rešenih podproblemov shranimo v tabelo, da se izognemo odvečnim izračunom.

Razčlenimo pristop od spodaj navzgor:

• Začne se z najmanjšimi podproblemi in se postopoma nadaljuje do končne rešitve.
• Izpolni tabelo z rešitvami podproblemov na način od spodaj navzgor.
• Primerno, kadar je število podproblemov majhno in je optimalno rešitev mogoče neposredno izračunati iz rešitev manjših podproblemov.

Dinamično programiranje (DP) Algoritem

Dinamično programiranje je algoritemska tehnika, ki rešuje kompleksne probleme tako, da jih razdeli na manjše podprobleme in shrani njihove rešitve za prihodnjo uporabo. Še posebej je učinkovit pri težavah, ki vsebujejo prekrivajočih se podproblemov in optimalno podkonstrukcijo.

Pogosti algoritmi, ki uporabljajo dinamično programiranje:

• Najdaljše skupno podzaporedje (LCS): Poišče najdaljše skupno podzaporedje med dvema nizoma.
• Najkrajša pot v grafu: Poišče najkrajšo pot med dvema vozliščema v grafu.
• Težava z nahrbtnikom: Določa največjo vrednost predmetov, ki jih je mogoče dati v nahrbtnik z dano kapaciteto.
• Matrično verižno množenje: Optimizira vrstni red množenja matrik, da zmanjša število operacij.
• Fibonaccijevo zaporedje: Izračuna n-to Fibonaccijevo število.

Prednosti dinamičnega programiranja (DP)

Dinamično programiranje ima številne prednosti, vključno z:

• Izogiba se večkratnemu ponovnemu izračunavanju istih podproblemov, kar vodi do znatnih prihrankov časa.
• Zagotavlja, da se najde optimalna rešitev z upoštevanjem vseh možnih kombinacij.
• Kompleksne probleme razdeli na manjše, bolj obvladljive podprobleme.

Aplikacije dinamičnega programiranja (DP)

Dinamično programiranje ima široko paleto aplikacij, vključno z:

• Optimizacija: Problem nahrbtnika, problem najkrajše poti, problem maksimalne podmatrike
• Računalništvo: Najdaljše skupno podzaporedje, razdalja urejanja, ujemanje nizov
• Operacijske raziskave: Upravljanje zalog, razporejanje, dodeljevanje virov

Zdaj pa raziščimo obsežen načrt za obvladovanje dinamičnega programiranja.

python ustvari uuid

Naučite se osnov dinamičnega programiranja (DP)

• Kaj je memoizacija? Popolna vadnica
• Tabelariranje proti memoizaciji
• Optimalna lastnost podkonstrukcije
• Lastnost prekrivajočih se podproblemov
• Kako rešiti problem dinamičnega programiranja?

• Fibonaccijeva števila
• n-ta katalonska številka
• Številke zvoncev (število načinov razdelitve niza)
• Binomski koeficient
• Težava z menjavo kovancev
• Problem vsote podnabora
• Izračunajte nCr % p
• Rezanje palice
• Algoritem za barvanje ograje
• Najdaljše skupno podzaporedje
• Najdaljše naraščajoče podzaporedje
• Najdaljše podzaporedje, tako da je razlika med sosednjima ena
• Kvadratna podmatrika največje velikosti z vsemi 1
• Pot minimalnih stroškov
• Najmanjše število skokov, da dosežete cilj
• Najdaljši skupni podniz (prostorsko optimizirana rešitev DP)
• Preštejte načine, kako doseči n-to stopnico s korakom 1, 2 ali 3
• Preštejte vse možne poti od zgornje leve do spodnje desne strani matrike mXn
• Edinstvene poti v mreži z ovirami

2. Srednje težave pri dinamičnem programiranju (DP)

• Floyd Warshallov algoritem
• Bellman-Fordov algoritem
• 0-1 Težava z nahrbtnikom
• Tiskanje predmetov v nahrbtniku 0/1
• Neomejen nahrbtnik (dovoljeno ponavljanje predmetov)
• Uganka padanja jajc
• Težava z lomljenjem besed
• Težava s pokrovom Vertex
• Težava z zlaganjem ploščic
• Težava z zlaganjem škatle
• Težava s particijo
• Problem trgovskega potnika | 1. sklop (naivno in dinamično programiranje)
• Najdaljše palindromsko zaporedje
• Najdaljše skupno naraščajoče podzaporedje (LCS + LIS)
• Poiščite vse različne vsote podnaborov (ali podzaporedij) matrike
• Ponderirano razporejanje dela
• Motnje štetja (takšna permutacija, da se noben element ne prikaže v prvotnem položaju)
• Najmanjši vstavki za oblikovanje palindroma
• Ujemanje z nadomestnimi znaki
• Načini razporeditve žog tako, da so sosednje žoge različnih vrst

3. Težke težave pri dinamičnem programiranju (DP)

• Palindromno particioniranje
• Težava s prelivanjem besed
• Slikarjev problem razdelitve
• Program za reševanje problema Bridge and Torch
• Matrično verižno množenje
• Tiskanje oklepajev v problemu matričnega verižnega množenja
• Pravokotnik z največjo vsoto v 2D matriki
• Največji dobiček z nakupom in prodajo delnice največ k-krat
• Najmanjši strošek za razvrščanje nizov z uporabo obratnih operacij različnih stroškov
• Število podzaporedij AP (aritmetična progresija) v matriki
• Uvod v dinamično programiranje na drevesih
• Največja višina drevesa, ko je katero koli vozlišče mogoče obravnavati kot koren
• Najdaljši ponavljajoči se in neprekrivajoči se podniz

Hitre povezave:

• Naučite se podatkovne strukture in algoritmov | Vadnica DSA
• 20 najboljših vprašanj za intervju o dinamičnem programiranju
• 'Težave za vajo' pri dinamičnem programiranju
• 'Kviz' o dinamičnem programiranju