Dinamično programiranje je tehnika, ki probleme razdeli na podprobleme in rezultat shrani za prihodnje namene, tako da nam rezultata ni treba znova izračunati. Podproblemi so optimizirani za optimizacijo celotne rešitve, kar je znano kot lastnost optimalne podstrukture. Glavna uporaba dinamičnega programiranja je reševanje problemov optimizacije. Tukaj optimizacijski problemi pomenijo, da poskušamo najti minimalno ali maksimalno rešitev problema. Dinamično programiranje zagotavlja najti optimalno rešitev problema, če rešitev obstaja.

Definicija dinamičnega programiranja pravi, da je to tehnika za reševanje kompleksnega problema tako, da najprej vdremo v zbirko enostavnejših podproblemov, rešimo vsak podproblem samo enkrat in nato shranimo njihove rešitve, da se izognemo ponavljajočim se izračunom.

Razumejmo ta pristop na primeru.

Razmislite o primeru Fibonaccijeve serije. Naslednja serija je Fibonaccijeva serija:

java ima naslednje

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…

Številke v zgornjem nizu niso naključno izračunane. Matematično bi lahko vsak izraz zapisali s spodnjo formulo:

F(n) = F(n-1) + F(n-2),

Z osnovnima vrednostma F(0) = 0 in F(1) = 1. Za izračun drugih števil sledimo zgornjemu razmerju. Na primer, F(2) je vsota f(0) in f(1), kar je enako 1.

Kako lahko izračunamo F(20)?

F(20) člen bo izračunan z uporabo n-te formule Fibonaccijeve vrste. Spodnja slika prikazuje, kako se izračuna F(20).

starost kylie jenner

Kot lahko opazimo na zgornji sliki, je F(20) izračunan kot vsota F(19) in F(18). Pri pristopu dinamičnega programiranja skušamo problem razdeliti na podobne podprobleme. Temu pristopu sledimo v zgornjem primeru, kjer je F(20) v podobna podproblema, tj. F(19) in F(18). Če povzamemo definicijo dinamičnega programiranja, ki pravi, da se podoben podproblem ne sme izračunati več kot enkrat. Kljub temu se v zgornjem primeru podproblem izračuna dvakrat. V zgornjem primeru je F(18) izračunan dvakrat; podobno se dvakrat izračuna tudi F(17). Vendar je ta tehnika zelo uporabna, saj rešuje podobne podprobleme, vendar moramo biti pri shranjevanju rezultatov previdni, ker nismo posebni pri shranjevanju rezultatov, ki smo jih izračunali enkrat, potem lahko to povzroči izgubo virov.

V zgornjem primeru, če izračunamo F(18) v desnem poddrevesu, to vodi do ogromne porabe virov in zmanjša splošno zmogljivost.

Rešitev zgornje težave je shranjevanje izračunanih rezultatov v polje. Najprej izračunamo F(16) in F(17) in njuni vrednosti shranimo v matriko. F(18) se izračuna s seštevanjem vrednosti F(17) in F(16), ki sta že shranjeni v matriki. Izračunana vrednost F(18) se shrani v matriko. Vrednost F(19) se izračuna z uporabo vsote F(18) in F(17), njuni vrednosti pa sta že shranjeni v matriki. Izračunana vrednost F(19) je shranjena v matriki. Vrednost F(20) je mogoče izračunati tako, da seštejete vrednosti F(19) in F(18), vrednosti obeh F(19) in F(18) pa so shranjene v matriki. Končna izračunana vrednost F(20) je shranjena v matriki.

Kako deluje pristop dinamičnega programiranja?

Sledijo koraki, ki jim sledi dinamično programiranje:

• Kompleksen problem razdeli na enostavnejše podprobleme.
• Za te podprobleme najde optimalno rešitev.
• Shranjuje rezultate podproblemov (memoizacija). Postopek shranjevanja rezultatov podproblemov je znan kot pomnjenje.
• Ponovno jih uporabi, tako da se isti podproblem izračuna večkrat.
• Na koncu izračunajte rezultat kompleksnega problema.

Zgornjih pet korakov je osnovnih korakov za dinamično programiranje. Dinamično programiranje je uporabno, če ima lastnosti, kot so:

tcp in ip model

Tisti problemi, ki imajo prekrivajoče se podprobleme in optimalne podstrukture. Pri tem optimalna podstruktura pomeni, da lahko rešitev optimizacijskih problemov dobimo s preprosto kombinacijo optimalne rešitve vseh podproblemov.

V primeru dinamičnega programiranja bi bila prostorska kompleksnost povečana, saj hranimo vmesne rezultate, časovna pa bi se zmanjšala.

Pristopi dinamičnega programiranja

Obstajata dva pristopa k dinamičnemu programiranju:

• Pristop od zgoraj navzdol
• Pristop od spodaj navzgor

Pristop od zgoraj navzdol

Pristop od zgoraj navzdol sledi tehniki pomnjenja, pristop od spodaj navzgor pa metodi tabeliranja. Tu je pomnjenje enako vsoti rekurzije in predpomnjenja. Rekurzija pomeni klic same funkcije, medtem ko predpomnjenje pomeni shranjevanje vmesnih rezultatov.

python ustvari uuid

Prednosti

• Je zelo enostaven za razumevanje in izvajanje.
• Podprobleme rešuje samo takrat, ko je to potrebno.
• Odpravljanje napak je enostavno.

Slabosti

Uporablja tehniko rekurzije, ki zasede več pomnilnika v skladu klicev. Včasih, ko je rekurzija pregloboka, pride do stanja prelivanja sklada.

Zavzame več pomnilnika, kar poslabša splošno delovanje.

Razumejmo dinamično programiranje na primeru.

 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 &apos;n&apos; 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&apos;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&apos;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)>