Dinaminis programavimas yra metodas, naudojamas matematikoje ir informatikoje sudėtingoms problemoms spręsti skaidant jas į paprastesnes dalis. Išsprendus kiekvieną antrinę problemą tik vieną kartą ir išsaugant rezultatus, išvengiama perteklinių skaičiavimų, todėl galima rasti efektyvesnių įvairių problemų sprendimų. Šiame straipsnyje pateikiamas išsamus dinaminio programavimo koncepcijų tyrimas, iliustruotas pavyzdžiais.

rihannos amžius

Dinaminis programavimas

Turinys

• Kas yra dinaminis programavimas?
• Kaip veikia dinaminis programavimas?
• Dinaminio programavimo pavyzdžiai
• Kada naudoti dinaminį programavimą?
• Dinaminio programavimo požiūriai
• Dinaminio programavimo algoritmas
• Dinaminio programavimo privalumai
• Dinaminio programavimo taikymai
• Išmokite dinaminio programavimo pagrindus
• Išplėstinės dinaminio programavimo sąvokos
• Dinaminio programavimo problemos

Kas yra dinaminis programavimas (DP)?

Dinaminis programavimas (DP) yra metodas, naudojamas matematikoje ir informatikoje sudėtingoms problemoms spręsti skaidant jas į paprastesnes dalis. Išsprendus kiekvieną antrinę problemą tik vieną kartą ir išsaugant rezultatus, išvengiama perteklinių skaičiavimų, o tai leidžia efektyviau išspręsti daugybę problemų.

Kaip veikia dinaminis programavimas (DP)?

• Nustatykite subproblemas: Padalinkite pagrindinę problemą į mažesnes, nepriklausomas subproblemas.
• Parduotuvės sprendimai: Išspręskite kiekvieną antrinę problemą ir išsaugokite sprendimą lentelėje arba masyve.
• Sukūrimo sprendimai: Naudokite saugomus sprendimus, kad sukurtumėte pagrindinės problemos sprendimą.
• Venkite pertekliaus: Išsaugodama sprendimus, DP užtikrina, kad kiekviena subproblema būtų išspręsta tik vieną kartą, taip sumažinant skaičiavimo laiką.

Dinaminio programavimo (DP) pavyzdžiai

1 pavyzdys: Apsvarstykite Fibonačio sekos radimo problemą:

Fibonačio seka: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Brutalios jėgos metodas:

Norėdami rasti n-ąjį Fibonačio skaičių naudodami brutalios jėgos metodą, tiesiog pridėkite (n-1)-oji ir (n-2)-oji Fibonačio skaičiai. Tai veiktų, bet būtų neefektyvu didelėms vertėms n , nes tam reikėtų apskaičiuoti visus ankstesnius Fibonačio skaičius.

Dinaminis programavimo metodas:

Fibonacci serija naudojant dinaminį programavimą

• Subproblemos: F(0), F(1), F(2), F(3), …
• Parduotuvės sprendimai: Sukurkite lentelę, kad išsaugotumėte F(n) reikšmes, kai jos skaičiuojamos.
• Sukūrimo sprendimai: F(n) lentelėje ieškokite F(n-1) ir F(n-2) ir pridėkite juos.
• Venkite pertekliaus: Lentelė užtikrina, kad kiekviena subproblema (pvz., F(2)) būtų išspręsta tik vieną kartą.

Naudodami DP, galime efektyviai apskaičiuoti Fibonačio seką, nereikalaujant perskaičiuoti subproblemų.

pridėti prie masyvo java

2 pavyzdys: Ilgiausia bendra poseka (ilgiausios posekos, bendros dviem eilutėms, radimas)

3 pavyzdys: Trumpiausias kelias grafike (trumpiausio kelio tarp dviejų grafiko mazgų radimas)

4 pavyzdys: Kuprinės problema (rasti maksimalią daiktų vertę, kurią galima įdėti į kuprinę su tam tikra talpa)

Kada naudoti dinaminį programavimą (DP)?

Dinaminis programavimas yra optimizavimo technika, naudojama sprendžiant problemas, kurią sudaro šios charakteristikos:

1. Optimali pagrindo struktūra:

Optimali postruktūra reiškia, kad mes sujungiame optimalius subproblemų rezultatus, kad pasiektume optimalų didesnės problemos rezultatą.

java metodai

Pavyzdys:

Apsvarstykite problemą ieškant minimalios išlaidos kelias svertiniame grafike nuo a šaltinis mazgas iki a Kelionės tikslas mazgas. Šią problemą galime suskirstyti į mažesnes dalis:

• Surask minimumas kaina kelias nuo šaltinis mazgas kiekvienam tarpinis mazgas.
• Surask minimumas kaina kelias iš kiekvieno tarpinis mazgas prie Kelionės tikslas mazgas.

Didesnės problemos sprendimas (minimalių sąnaudų kelio nuo šaltinio mazgo iki paskirties mazgo radimas) gali būti sudarytas iš šių mažesnių subproblemų sprendimų.

2. Sutampančios poproblemos:

Tos pačios subproblemos sprendžiamos pakartotinai skirtingose ​​problemos dalyse.

Pavyzdys:

Apsvarstykite skaičiavimo problemą Fibonačio serija . Norėdami apskaičiuoti Fibonačio skaičių indekse n , turime apskaičiuoti Fibonačio skaičius indeksuose n-1 ir n-2 . Tai reiškia, kad Fibonačio skaičiaus skaičiavimo indekse antrinė problema n-1 yra naudojamas du kartus sprendžiant didesnę Fibonačio skaičiaus indekso skaičiavimo problemą n .

Dinaminio programavimo (DP) metodai

Dinaminį programavimą galima pasiekti dviem būdais:

1. Metodas iš viršaus į apačią (atmintinė):

Taikant metodą iš viršaus į apačią, dar vadinamą atmintinė , pradedame nuo galutinio sprendimo ir rekursyviai suskaidome jį į smulkesnes dalis. Kad išvengtume perteklinių skaičiavimų, išspręstų subproblemų rezultatus saugome atmintinės lentelėje.

Išskirkime metodą iš viršaus į apačią:

• Pradedama nuo galutinio sprendimo ir rekursyviai suskaido jį į smulkesnes dalis.
• Išsaugo antrinių problemų sprendimus lentelėje, kad būtų išvengta perteklinių skaičiavimų.
• Tinka, kai subproblemų skaičius yra didelis ir daugelis jų naudojami pakartotinai.

2. Metodas iš apačios į viršų (lentelės):

Taikant metodą „iš apačios į viršų“, taip pat žinomas kaip lentelės sudarymas , pradedame nuo mažiausių subproblemų ir palaipsniui sukuriame iki galutinio sprendimo. Išspręstų subproblemų rezultatus saugome lentelėje, kad išvengtume perteklinių skaičiavimų.

Išskirkime metodą „iš apačios į viršų“:

• Pradedama nuo mažiausių subproblemų ir palaipsniui sukuriama iki galutinio sprendimo.
• Užpildo lentelę su subproblemų sprendimais „iš apačios į viršų“.
• Tinka, kai subproblemų skaičius yra mažas ir optimalų sprendimą galima tiesiogiai apskaičiuoti nuo sprendimų iki mažesnių subproblemų.

Dinaminis programavimas (DP) Algoritmas

Dinaminis programavimas yra algoritminė technika, kuri išsprendžia sudėtingas problemas suskaidant jas į smulkesnes problemas ir išsaugodama jų sprendimus būsimam naudojimui. Tai ypač veiksminga esant problemoms, kuriose yra persidengiančios subproblemos ir optimali substruktūra.

Įprasti algoritmai, naudojantys dinaminį programavimą:

• Ilgiausia bendra seka (LCS): Suranda ilgiausią bendrą dviejų eilučių seką.
• Trumpiausias kelias diagramoje: Suranda trumpiausią kelią tarp dviejų grafiko mazgų.
• Kuprinės problema: Nustato didžiausią daiktų, kuriuos galima įdėti į tam tikros talpos kuprinę, vertę.
• Matricos grandinės dauginimas: Optimizuoja matricos daugybos tvarką, kad sumažintų operacijų skaičių.
• Fibonačio seka: Apskaičiuoja n-ąjį Fibonačio skaičių.

Dinaminio programavimo privalumai (DP)

Dinaminis programavimas turi daug privalumų, įskaitant:

primityvūs duomenų tipai Java

• Neleidžiama perskaičiuoti tų pačių antrinių problemų kelis kartus, todėl sutaupoma daug laiko.
• Užtikrina, kad būtų rastas optimalus sprendimas, įvertinus visus galimus derinius.
• Suskaido sudėtingas problemas į mažesnes, lengviau valdomas problemas.

Dinaminio programavimo taikymai (DP)

Dinaminis programavimas turi platų programų spektrą, įskaitant:

• Optimizavimas: Kuprinės problema, trumpiausio kelio problema, didžiausio porūšio problema
• Kompiuteriai: Ilgiausia bendra seka, redagavimo atstumas, eilučių atitikimas
• Operacijų tyrimas: Atsargų valdymas, planavimas, išteklių paskirstymas

Dabar panagrinėkime išsamų dinaminio programavimo įvaldymo planą.

Išmokite dinaminio programavimo (DP) pagrindus

• Kas yra atmintinė? Pilna pamoka
• Lentelių sudarymas prieš memoizaciją
• Optimali pagrindo savybė
• Sutampančių subproblemų savybė
• Kaip išspręsti dinaminio programavimo problemą?

• Fibonačio skaičiai
• n-asis katalonų numeris
• Skambučių numeriai (rinkinio padalijimo būdų skaičius)
• Binominis koeficientas
• Monetos keitimo problema
• Pogrupio sumos problema
• Apskaičiuokite nCr % p
• Strypo pjovimas
• Dažymo tvoros algoritmas
• Ilgiausia bendra seka
• Ilgiausiai didėjanti seka
• Ilgiausia seka, kad skirtumas tarp gretimų yra vienas
• Maksimalaus dydžio kvadratinė submatrica su visais 1s
• Minimalios kainos kelias
• Minimalus šuolių skaičius, kad pasiektumėte pabaigą
• Ilgiausia bendroji poeilutė (erdvės optimizuotas DP sprendimas)
• Suskaičiuokite būdus, kaip pasiekti n-tuosius laiptus, atlikdami 1, 2 arba 3 žingsnius
• Suskaičiuokite visus galimus mXn matricos kelius iš viršutinės kairės į apačią dešinėje
• Unikalūs takai tinklelyje su kliūtimis

2. Vidutinės dinaminio programavimo (DP) problemos

• Floydo Warshall algoritmas
• Bellman-Ford algoritmas
• 0-1 Kuprinės problema
• Prekių spausdinimas 0/1 kuprinėje
• Neribota kuprinė (leidžiamas daiktų kartojimas)
• Kiaušinių numetimo dėlionė
• Žodžių lūžio problema
• Viršūnių dangtelio problema
• Plytelių klojimo problema
• Dėžutės sukrovimo problema
• Perskirstymo problema
• Keliaujančio pardavėjo problema | 1 rinkinys (naivus ir dinaminis programavimas)
• Ilgiausia palindrominė seka
• Ilgiausia bendra didėjanti seka (LCS + LIS)
• Raskite visas skirtingas masyvo poaibių (arba posekių) sumas
• Svertinis darbo planavimas
• Nukrypimų skaičius (permutacija, kad joks elementas neatsirastų pradinėje padėtyje)
• Minimalūs įterpimai, kad susidarytų palindromas
• Pakaitos simbolių modelio atitikimas
• Būdai, kaip išdėstyti kamuoliukus taip, kad šalia esantys rutuliai būtų skirtingų tipų

3. Sunkios dinaminio programavimo (DP) problemos

• Palindromo skaidymas
• Žodžių vyniojimo problema
• Dailininko pertvaros problema
• Programa tilto ir deglo problemai spręsti
• Matricos grandinės dauginimas
• Spausdinimo skliausteliuose Matricos grandinės daugybos problema
• Didžiausia stačiakampio suma 2D matricoje
• Maksimalus pelnas perkant ir parduodant akciją daugiausia k kartų
• Minimali kaina rūšiuojant eilutes naudojant skirtingų išlaidų apvertimo operacijas
• AP (aritmetinės progresijos) posekių skaičius masyve
• Dinaminio programavimo medžiuose įvadas
• Maksimalus medžio aukštis, kai bet kuris mazgas gali būti laikomas šaknimis
• Ilgiausia pasikartojanti ir nepersidengianti eilutė

Greitos nuorodos:

• Sužinokite duomenų struktūrą ir algoritmus | DSA mokymo programa
• 20 geriausių dinaminio programavimo interviu klausimų
• Dinaminio programavimo „Praktikos problemos“.
• „Viktorina“ apie dinaminį programavimą