Dinamiskā programmēšana ir paņēmiens, kas sadala problēmas apakšproblēmās un saglabā rezultātu nākotnes vajadzībām, lai rezultāts nebūtu jāaprēķina vēlreiz. Apakšproblēmas ir optimizētas, lai optimizētu kopējo risinājumu, ko sauc par optimālu apakšstruktūras īpašību. Dinamiskās programmēšanas galvenais pielietojums ir optimizācijas problēmu risināšana. Šeit optimizācijas problēmas nozīmē, kad mēs cenšamies noskaidrot problēmas minimālo vai maksimālo risinājumu. Dinamiskā programmēšana garantē optimāla problēmas risinājuma atrašanu, ja risinājums pastāv.
Dinamiskās programmēšanas definīcija saka, ka tā ir sarežģītas problēmas risināšanas paņēmiens, vispirms ielaužoties vienkāršāku apakšproblēmu kolekcijā, katru apakšproblēmu atrisinot tikai vienu reizi un pēc tam saglabājot to risinājumus, lai izvairītos no atkārtotiem aprēķiniem.
Izpratīsim šo pieeju, izmantojot piemēru.
Apsveriet Fibonači sērijas piemēru. Šāda sērija ir Fibonači sērija:
iegūt pašreizējo datumu java
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Skaitļi iepriekš minētajās sērijās nav nejauši aprēķināti. Matemātiski mēs varētu uzrakstīt katru no terminiem, izmantojot šādu formulu:
F(n) = F(n-1) + F(n-2),
Ar bāzes vērtībām F(0) = 0 un F(1) = 1. Lai aprēķinātu pārējos skaitļus, mēs sekojam iepriekšminētajai sakarībai. Piemēram, F(2) ir summa f(0) un f(1), kas ir vienāds ar 1.
Kā mēs varam aprēķināt F(20)?
F(20) termins tiks aprēķināts, izmantojot Fibonači sērijas n-to formulu. Zemāk redzamajā attēlā parādīts, kā tiek aprēķināts F(20).
virkņu masīvs c
Kā redzams iepriekš attēlā, F(20) tiek aprēķināts kā F(19) un F(18) summa. Dinamiskās programmēšanas pieejā mēs cenšamies sadalīt problēmu līdzīgās apakšproblēmās. Mēs sekojam šai pieejai iepriekš minētajā gadījumā, kur F (20) līdzīgās apakšproblēmās, t.i., F (19) un F (18). Ja mēs atkārtojam dinamiskās programmēšanas definīciju, tajā teikts, ka līdzīgu apakšproblēmu nevajadzētu aprēķināt vairāk kā vienu reizi. Tomēr iepriekš minētajā gadījumā apakšproblēma tiek aprēķināta divreiz. Iepriekš minētajā piemērā F(18) tiek aprēķināts divas reizes; līdzīgi arī F(17) tiek aprēķināts divreiz. Tomēr šis paņēmiens ir diezgan noderīgs, jo tas atrisina līdzīgas apakšproblēmas, taču mums ir jābūt piesardzīgiem, saglabājot rezultātus, jo mēs īpaši neuzglabājam rezultātu, ko esam aprēķinājuši vienu reizi, tad tas var novest pie resursu izšķērdēšanas.
Iepriekš minētajā piemērā, ja mēs aprēķinām F(18) labajā apakškokā, tas noved pie milzīga resursu izmantošanas un samazina kopējo veiktspēju.
Iepriekš minētās problēmas risinājums ir saglabāt aprēķinātos rezultātus masīvā. Pirmkārt, mēs aprēķinām F(16) un F(17) un saglabājam to vērtības masīvā. F(18) tiek aprēķināts, summējot F(17) un F(16) vērtības, kas jau ir saglabātas masīvā. F(18) aprēķinātā vērtība tiek saglabāta masīvā. F(19) vērtību aprēķina, izmantojot F(18) un F(17) summu, un to vērtības jau ir saglabātas masīvā. F(19) aprēķinātā vērtība tiek saglabāta masīvā. F(20) vērtību var aprēķināt, saskaitot F(19) un F(18) vērtības, un gan F(19), gan F(18) vērtības tiek saglabātas masīvā. F(20) galīgā aprēķinātā vērtība tiek saglabāta masīvā.
Kā darbojas dinamiskās programmēšanas pieeja?
Tālāk ir norādītas dinamiskās programmēšanas darbības.
- Tas sadala sarežģīto problēmu vienkāršākos apakšproblēmās.
- Tā atrod optimālo risinājumu šīm apakšproblēmām.
- Tajā tiek saglabāti apakšproblēmu rezultāti (atgādināšana). Apakšproblēmu rezultātu saglabāšanas process ir pazīstams kā iegaumēšana.
- Tas tos izmanto atkārtoti, lai viena un tā pati apakšproblēma tiktu aprēķināta vairāk nekā vienu reizi.
- Visbeidzot, aprēķiniet sarežģītās problēmas rezultātu.
Iepriekš minētie pieci soļi ir dinamiskās programmēšanas pamata soļi. Ir piemērojama dinamiskā programmēšana, kurai ir tādas īpašības kā:
Madhuri teica, nāc
Problēmas, kurās pārklājas apakšproblēmas un optimālas apakšstruktūras. Šeit optimāla apakšstruktūra nozīmē, ka optimizācijas uzdevumu risinājumu var iegūt, vienkārši apvienojot visu apakšproblēmu optimālo risinājumu.
Dinamiskās programmēšanas gadījumā, saglabājot starprezultātus, telpas sarežģītība palielinātos, bet laika sarežģītība samazinātos.
Dinamiskās programmēšanas pieejas
Dinamiskajai programmēšanai ir divas pieejas:
- No augšas uz leju pieeja
- Augšupēja pieeja
No augšas uz leju pieeja
Lejupējai pieejai tiek izmantota iegaumēšanas tehnika, savukārt augšupējā pieeja seko tabulēšanas metodei. Šeit iegaumēšana ir vienāda ar rekursijas un kešatmiņas summu. Rekursija nozīmē pašas funkcijas izsaukšanu, savukārt kešatmiņa nozīmē starprezultātu saglabāšanu.
js ielāde
Priekšrocības
- To ir ļoti viegli saprast un īstenot.
- Tas atrisina apakšproblēmas tikai tad, kad tas ir nepieciešams.
- To ir viegli atkļūdot.
Trūkumi
Tas izmanto rekursijas paņēmienu, kas aizņem vairāk atmiņas zvanu kaudzē. Dažreiz, kad rekursija ir pārāk dziļa, rodas steka pārpildes nosacījums.
Tas aizņem vairāk atmiņas, kas pasliktina kopējo veiktspēju.
Izpratīsim dinamisko programmēšanu, izmantojot piemēru.
int fib(int n) { if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); } < pre> <p>In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of 'n' increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2<sup>n</sup>.</p> <p>One solution to this problem is to use the dynamic programming approach. Rather than generating the recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic programming approach, then the time complexity would be O(n).</p> <p>When we apply the dynamic programming approach in the implementation of the Fibonacci series, then the code would look like:</p> <pre> static int count = 0; int fib(int n) { if(memo[n]!= NULL) return memo[n]; count++; if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); memo[n]="sum;" } < pre> <p>In the above code, we have used the memorization technique in which we store the results in an array to reuse the values. This is also known as a top-down approach in which we move from the top and break the problem into sub-problems.</p> <h3>Bottom-Up approach</h3> <p>The bottom-up approach is also one of the techniques which can be used to implement the dynamic programming. It uses the tabulation technique to implement the dynamic programming approach. It solves the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the problems and store the results in a matrix.</p> <p>There are two ways of applying dynamic programming:</p> <ul> <tr><td>Top-Down</td> </tr><tr><td>Bottom-Up</td> </tr></ul> <p>The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base cases, so we will start from 0 and 1.</p> <p> <strong>Key points</strong> </p> <ul> <li>We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then move to the larger problems using smaller sub-problems.</li> <li>We use for loop to iterate over the sub-problems.</li> <li>The bottom-up approach is also known as the tabulation or table filling method.</li> </ul> <p> <strong>Let's understand through an example.</strong> </p> <p>Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions, respectively shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-2.webp" alt="Dynamic Programming"> <p>Since the bottom-up approach starts from the lower values, so the values at a[0] and a[1] are added to find the value of a[2] shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-3.webp" alt="Dynamic Programming"> <p>The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-4.webp" alt="Dynamic Programming"> <p>The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-5.webp" alt="Dynamic Programming"> <p>The value of a[5] will be calculated by adding the values of a[4] and a[3], and it becomes 5 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-6.webp" alt="Dynamic Programming"> <p>The code for implementing the Fibonacci series using the bottom-up approach is given below:</p> <pre> int fib(int n) { int A[]; A[0] = 0, A[1] = 1; for( i=2; i<=n; i++) { a[i]="A[i-1]" + a[i-2] } return a[n]; < pre> <p>In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci series.</p> <p> <strong>Let's understand through the diagrammatic representation.</strong> </p> <p>Initially, the first two values, i.e., 0 and 1 can be represented as:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-7.webp" alt="Dynamic Programming"> <p>When i=2 then the values 0 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-8.webp" alt="Dynamic Programming"> <p>When i=3 then the values 1and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-9.webp" alt="Dynamic Programming"> <p>When i=4 then the values 2 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-10.webp" alt="Dynamic Programming"> <p>When i=5, then the values 3 and 2 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-11.webp" alt="Dynamic Programming"> <p>In the above case, we are starting from the bottom and reaching to the top.</p> <hr></=n;></pre></0)></pre></0)>