Dinamiskā programmēšana ir metode, ko izmanto matemātikā un datorzinātnēs, lai atrisinātu sarežģītas problēmas, sadalot tās vienkāršākos apakšproblēmās. Atrisinot katru apakšproblēmu tikai vienu reizi un saglabājot rezultātus, tas ļauj izvairīties no liekiem aprēķiniem, tādējādi radot efektīvākus risinājumus plašam problēmu lokam. Šajā rakstā ir sniegta detalizēta dinamiskās programmēšanas koncepciju izpēte, kas ilustrēta ar piemēriem.

iegūt pašreizējo datumu java

Dinamiskā programmēšana

Satura rādītājs

• Kas ir dinamiskā programmēšana?
• Kā darbojas dinamiskā programmēšana?
• Dinamiskās programmēšanas piemēri
• Kad izmantot dinamisko programmēšanu?
• Dinamiskās programmēšanas pieejas
• Dinamiskās programmēšanas algoritms
• Dinamiskās programmēšanas priekšrocības
• Dinamiskās programmēšanas pielietojumi
• Apgūstiet dinamiskās programmēšanas pamatus
• Uzlabotas dinamiskās programmēšanas koncepcijas
• Dinamiskās programmēšanas problēmas

Kas ir dinamiskā programmēšana (DP)?

Dinamiskā programmēšana (DP) ir metode, ko izmanto matemātikā un datorzinātnēs, lai atrisinātu sarežģītas problēmas, sadalot tās vienkāršākos apakšproblēmās. Atrisinot katru apakšproblēmu tikai vienu reizi un saglabājot rezultātus, tas ļauj izvairīties no liekiem aprēķiniem, tādējādi radot efektīvākus risinājumus plašam problēmu lokam.

Kā darbojas dinamiskā programmēšana (DP)?

• Apakšproblēmu noteikšana: Sadaliet galveno problēmu mazākās, neatkarīgās apakšproblēmās.
• Veikala risinājumi: Atrisiniet katru apakšproblēmu un saglabājiet risinājumu tabulā vai masīvā.
• Veidošanas risinājumi: Izmantojiet saglabātos risinājumus, lai izveidotu galvenās problēmas risinājumu.
• Izvairieties no atlaišanas: Saglabājot risinājumus, DP nodrošina, ka katra apakšproblēma tiek atrisināta tikai vienreiz, tādējādi samazinot aprēķina laiku.

Dinamiskās programmēšanas (DP) piemēri

1. piemērs: Apsveriet Fibonači secības atrašanas problēmu:

Fibonači secība: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Brutālā spēka pieeja:

Lai atrastu n-to Fibonači skaitli, izmantojot brutālā spēka pieeju, jums vienkārši jāpievieno (n-1) un (n-2) Fibonači skaitļi. Tas darbotos, taču tas būtu neefektīvi lielām vērtībām n , jo tas prasītu visu iepriekšējo Fibonači skaitļu aprēķinu.

Dinamiskās programmēšanas pieeja:

Fibonači sērija, izmantojot dinamisko programmēšanu

• Apakšproblēmas: F(0), F(1), F(2), F(3), …
• Veikala risinājumi: Izveidojiet tabulu, lai saglabātu F(n) vērtības, kad tās tiek aprēķinātas.
• Veidošanas risinājumi: F(n) tabulā atrodiet F(n-1) un F(n-2) un pievienojiet tos.
• Izvairieties no atlaišanas: Tabula nodrošina, ka katra apakšproblēma (piemēram, F(2)) tiek atrisināta tikai vienu reizi.

Izmantojot DP, mēs varam efektīvi aprēķināt Fibonači secību, nepārrēķinot apakšproblēmas.

virkņu masīvs c

2. piemērs: Garākā kopīgā apakšsecība (garākās apakšsecības atrašana, kas ir kopīga divām virknēm)

3. piemērs: Īsākais ceļš grafikā (īsākā ceļa atrašana starp diviem diagrammas mezgliem)

4. piemērs: Problēma ar mugursomu (noskaidrojot to priekšmetu maksimālo vērtību, ko var ievietot mugursomā ar noteiktu ietilpību)

Kad izmantot dinamisko programmēšanu (DP)?

Dinamiskā programmēšana ir optimizācijas paņēmiens, ko izmanto problēmu risināšanā, kas sastāv no šādiem raksturlielumiem:

1. Optimāla apakšstruktūra:

Optimāla apakšstruktūra nozīmē, ka mēs apvienojam apakšproblēmu optimālos rezultātus, lai sasniegtu lielākās problēmas optimālo rezultātu.

Madhuri teica, nāc

Piemērs:

Apsveriet problēmu, kā atrast minimālās izmaksas ceļš svērtā grafikā no a avots mezgls uz a galamērķis mezgls. Mēs varam sadalīt šo problēmu mazākās apakšproblēmās:

• Atrodi minimums izmaksas ceļš no avots mezgls katram starpposma mezgls.
• Atrodi minimums izmaksas ceļš no katra starpposma mezgls uz galamērķis mezgls.

Lielākas problēmas risinājumu (minimālo izmaksu ceļa atrašana no avota mezgla līdz galamērķa mezglam) var izveidot no šo mazāko apakšproblēmu risinājumiem.

2. Apakšproblēmas, kas pārklājas:

Tās pašas apakšproblēmas tiek atrisinātas atkārtoti dažādās problēmas daļās.

Piemērs:

Apsveriet skaitļošanas problēmu Fibonači sērija . Lai aprēķinātu Fibonači skaitli indeksā n , mums jāaprēķina Fibonači skaitļi indeksos n-1 un n-2 . Tas nozīmē, ka Fibonači skaitļa aprēķināšanas apakšproblēma indeksā n-1 tiek izmantots divreiz, risinot lielāku problēmu, kas saistīta ar Fibonači skaitļa aprēķināšanu indeksā n .

Dinamiskās programmēšanas (DP) pieejas

Dinamisku programmēšanu var veikt, izmantojot divas pieejas:

1. No augšas uz leju pieeja (atgādināšana):

Pieejā no augšas uz leju, kas pazīstama arī kā iegaumēšana , mēs sākam ar gala risinājumu un rekursīvi sadalām to mazākās apakšproblēmās. Lai izvairītos no liekiem aprēķiniem, atrisināto apakšproblēmu rezultātus uzglabājam memoizācijas tabulā.

Sadalīsim pieeju no augšas uz leju:

• Sākas ar galīgo risinājumu un rekursīvi sadala to mazākās apakšproblēmās.
• Saglabā apakšproblēmu risinājumus tabulā, lai izvairītos no liekiem aprēķiniem.
• Piemērots, ja apakšproblēmu skaits ir liels un daudzas no tām tiek izmantotas atkārtoti.

2. Augšupēja pieeja (tabulācijas):

Augšupējā pieejā, kas pazīstama arī kā tabulēšana , mēs sākam ar mazākajām apakšproblēmām un pakāpeniski veidojam līdz galīgajam risinājumam. Atrisināto apakšproblēmu rezultātus uzglabājam tabulā, lai izvairītos no liekiem aprēķiniem.

Sadalīsim augšupēju pieeju:

js ielāde

• Sākas ar mazākajām apakšproblēmām un pakāpeniski attīstās līdz galīgajam risinājumam.
• Aizpilda tabulu ar apakšproblēmu risinājumiem augšupvērsti.
• Piemērots, ja apakšproblēmu skaits ir mazs un optimālo risinājumu var tieši aprēķināt no risinājumiem uz mazākām apakšproblēmām.

Dinamiskā programmēšana (DP) Algoritms

Dinamiskā programmēšana ir algoritmisks paņēmiens, kas atrisina sarežģītas problēmas, sadalot tās mazākās apakšproblēmās un saglabājot to risinājumus turpmākai lietošanai. Tas ir īpaši efektīvs problēmām, kas satur apakšproblēmas, kas pārklājas un optimāla apakšstruktūra.

Izplatīti algoritmi, kas izmanto dinamisko programmēšanu:

• Garākā kopējā secība (LCS): Atrod garāko kopīgo apakšsecību starp divām virknēm.
• Īsākais ceļš diagrammā: Atrod īsāko ceļu starp diviem diagrammas mezgliem.
• Problēma ar mugursomu: Nosaka maksimālo priekšmetu vērtību, ko var ievietot mugursomā ar noteiktu ietilpību.
• Matricas ķēdes reizināšana: Optimizē matricas reizināšanas secību, lai samazinātu darbību skaitu.
• Fibonači secība: Aprēķina n-to Fibonači skaitli.

Dinamiskās programmēšanas priekšrocības (DP)

Dinamiskajai programmēšanai ir daudz priekšrocību, tostarp:

• Novērš vienu un to pašu apakšproblēmu pārrēķinu vairākas reizes, tādējādi ievērojami ietaupot laiku.
• Nodrošina optimālā risinājuma atrašanu, apsverot visas iespējamās kombinācijas.
• Sarežģītās problēmas sadala mazākās, vieglāk pārvaldāmās apakšproblēmās.

Dinamiskās programmēšanas pielietojumi (DP)

Dinamiskajai programmēšanai ir plašs lietojumu klāsts, tostarp:

• Optimizācija: Mugursomas problēma, īsākā ceļa problēma, maksimālā apakšgrupas problēma
• Datorzinātne: Garākā kopīgā apakšsecība, rediģēšanas attālums, virknes atbilstība
• Operāciju izpēte: Krājumu vadība, plānošana, resursu sadale

Tagad izpētīsim visaptverošu ceļvedi dinamiskās programmēšanas apguvei.

Apgūstiet dinamiskās programmēšanas (DP) pamatus

• Kas ir memoizācija? Pilnīga apmācība
• Tabulēšana pret memoizāciju
• Optimāla apakšstruktūras īpašība
• Pārklāšanās apakšproblēmu īpašums
• Kā atrisināt dinamiskās programmēšanas problēmu?

• Fibonači skaitļi
• n-tais katalāņu numurs
• Zvanu numuri (kopas sadalīšanas veidu skaits)
• Binomiālais koeficients
• Monētu maiņas problēma
• Apakškopas summas problēma
• Aprēķināt nCr % p
• Stieņa griešana
• Žogu krāsošanas algoritms
• Garākā kopējā secība
• Visilgākā pieaugošā secība
• Garākā apakšsecība, kurā starpība starp blakus esošajām ir viena
• Maksimālā izmēra kvadrātveida apakšmatrica ar visiem 1
• Minimālo izmaksu ceļš
• Minimālais lēcienu skaits, lai sasniegtu beigas
• Garākā kopējā apakšvirkne (kosmosam optimizēts DP risinājums)
• Saskaitiet veidus, kā sasniegt n-tās kāpnes, izmantojot 1., 2. vai 3. darbību
• Saskaitiet visus iespējamos ceļus no mXn matricas augšējās kreisās puses uz apakšējo labo pusi
• Unikāli ceļi režģī ar šķēršļiem

2. Vidējas dinamiskās programmēšanas (DP) problēmas

• Floida Voršala algoritms
• Bellman-Ford algoritms
• 0-1 mugursomas problēma
• Preču drukāšana 0/1 mugursomā
• Neierobežota mugursoma (atļauta priekšmetu atkārtošana)
• Olu nomešanas mīkla
• Vārdu pārtraukuma problēma
• Virsotnes seguma problēma
• Flīžu sakraušanas problēma
• Kastes sakraušanas problēma
• Sadalījuma problēma
• Ceļojošā pārdevēja problēma | 1. kopa (naivā un dinamiskā programmēšana)
• Garākā palindromiskā secība
• Garākā kopējā pieaugošā secība (LCS + LIS)
• Atrodiet visas atšķirīgās masīva apakškopas (vai apakšsecības) summas
• Svērtā darba plānošana
• Skaitīt novirzes (permutācija, lai neviens elements neparādās sākotnējā pozīcijā)
• Minimālais ievietojums, lai izveidotu palindromu
• Aizstājējzīmju raksta atbilstība
• Veidi, kā sakārtot bumbiņas tā, lai blakus esošās bumbiņas būtu dažāda veida

3. Sarežģītas dinamiskās programmēšanas (DP) problēmas

• Palindroma sadalīšana
• Vārdu aplaušanas problēma
• Gleznotāja nodalījuma problēma
• Programma tilta un lāpas problēmai
• Matricas ķēdes reizināšana
• Iekavu drukāšana matricas ķēdes reizināšanas uzdevumā
• Maksimālā taisnstūra summa 2D matricā
• Maksimālā peļņa, pērkot un pārdodot akciju ne vairāk kā k reizes
• Minimālās izmaksas, lai kārtotu virknes, izmantojot dažādu izmaksu apvēršanas darbības
• AP (aritmētiskās progresēšanas) apakšsekvenču skaits masīvā
• Ievads dinamiskajā programmēšanā uz kokiem
• Maksimālais koka augstums, kad jebkuru mezglu var uzskatīt par sakni
• Garākā atkārtotā un nepārklājošā apakšvirkne

Ātrās saites:

• Uzziniet datu struktūru un algoritmus | DSA apmācība
• 20 populārākie dinamiskās programmēšanas intervijas jautājumi
• Dinamiskās programmēšanas “prakses problēmas”.
• “Viktorīna” par dinamisko programmēšanu