Programarea dinamică este o tehnică care împarte problemele în sub-probleme și salvează rezultatul pentru scopuri viitoare, astfel încât să nu fie nevoie să calculăm rezultatul din nou. Subproblemele sunt optimizate pentru a optimiza soluția generală este cunoscută ca proprietatea optimă a substructurii. Principala utilizare a programării dinamice este rezolvarea problemelor de optimizare. Aici, problemele de optimizare înseamnă că atunci când încercăm să aflăm soluția minimă sau maximă a unei probleme. Programarea dinamică garantează găsirea soluției optime a unei probleme dacă soluția există.

Definiția programării dinamice spune că este o tehnică de rezolvare a unei probleme complexe prin spargerea mai întâi într-o colecție de subprobleme mai simple, rezolvând fiecare subproblemă doar o singură dată și apoi stocând soluțiile lor pentru a evita calculele repetitive.

Să înțelegem această abordare printr-un exemplu.

Luați în considerare un exemplu al seriei Fibonacci. Următoarea serie este seria Fibonacci:

idee intellij vs eclipsă

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

Numerele din seria de mai sus nu sunt calculate aleatoriu. Din punct de vedere matematic, am putea scrie fiecare dintre termeni folosind formula de mai jos:

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

Cu valorile de bază F(0) = 0 și F(1) = 1. Pentru a calcula celelalte numere, urmărim relația de mai sus. De exemplu, F(2) este suma f(0) și f(1), care este egal cu 1.

Cum putem calcula F(20)?

Termenul F(20) va fi calculat folosind a n-a formulă a seriei Fibonacci. Figura de mai jos arată cum se calculează F(20).

cum să accesezi fotografiile icloud

După cum putem observa în figura de mai sus, că F(20) se calculează ca sumă a lui F(19) și F(18). În abordarea de programare dinamică, încercăm să împărțim problema în subprobleme similare. Urmăm această abordare în cazul de mai sus în care F(20) în subprobleme similare, adică F(19) și F(18). Dacă recapitulăm definiția programării dinamice, spune că subproblema similară nu trebuie calculată de mai multe ori. Totuși, în cazul de mai sus, subproblema este calculată de două ori. În exemplul de mai sus, F(18) este calculat de două ori; în mod similar, F(17) este de asemenea calculat de două ori. Cu toate acestea, această tehnică este destul de utilă, deoarece rezolvă subproblemele similare, dar trebuie să fim precauți în timpul stocării rezultatelor, deoarece nu suntem specializați în stocarea rezultatului pe care l-am calculat o dată, atunci poate duce la o risipă de resurse.

În exemplul de mai sus, dacă calculăm F(18) în subarborele din dreapta, atunci aceasta duce la utilizarea extraordinară a resurselor și scade performanța generală.

Soluția la problema de mai sus este salvarea rezultatelor calculate într-o matrice. Mai întâi, calculăm F(16) și F(17) și salvăm valorile lor într-o matrice. F(18) se calculează prin însumarea valorilor lui F(17) și F(16), care sunt deja salvate într-o matrice. Valoarea calculată a lui F(18) este salvată într-un tablou. Valoarea lui F(19) este calculată folosind suma lui F(18) și F(17), iar valorile lor sunt deja salvate într-o matrice. Valoarea calculată a lui F(19) este stocată într-o matrice. Valoarea lui F(20) poate fi calculată prin adăugarea valorilor lui F(19) și F(18), iar valorile ambelor F(19) și F(18) sunt stocate într-o matrice. Valoarea finală calculată a lui F(20) este stocată într-o matrice.

Cum funcționează abordarea de programare dinamică?

Următorii sunt pașii pe care îi urmează programarea dinamică:

• Descompune problema complexă în subprobleme mai simple.
• Găsește soluția optimă pentru aceste sub-probleme.
• Stochează rezultatele subproblemelor (memorizare). Procesul de stocare a rezultatelor subproblemelor este cunoscut sub numele de memorare.
• Le reutiliza, astfel încât aceeași subproblemă să fie calculată de mai multe ori.
• În cele din urmă, calculați rezultatul problemei complexe.

Cei cinci pași de mai sus sunt pașii de bază pentru programarea dinamică. Se aplică programarea dinamică care au proprietăți precum:

data java la șir

Acele probleme care au subprobleme suprapuse și substructuri optime. Aici, substructură optimă înseamnă că soluția problemelor de optimizare poate fi obținută prin simpla combinare a soluției optime a tuturor subproblemelor.

În cazul programării dinamice, complexitatea spațiului ar fi crescută pe măsură ce stocăm rezultatele intermediare, dar complexitatea timpului ar fi scăzută.

Abordări ale programării dinamice

Există două abordări ale programării dinamice:

• Abordare de sus în jos
• Abordarea de jos în sus

Abordare de sus în jos

Abordarea de sus în jos urmează tehnica de memorare, în timp ce abordarea de jos în sus urmează metoda tabelării. Aici memorarea este egală cu suma recursiunii și a stocării în cache. Recursiunea înseamnă apelarea funcției în sine, în timp ce stocarea în cache înseamnă stocarea rezultatelor intermediare.

Avantaje

rând vs coloană

• Este foarte ușor de înțeles și implementat.
• Rezolvă subproblemele numai atunci când este necesar.
• Este ușor de depanat.

Dezavantaje

Utilizează tehnica recursiunii care ocupă mai multă memorie în stiva de apeluri. Uneori, când recursiunea este prea profundă, va apărea condiția de depășire a stivei.

Ocupă mai multă memorie, ceea ce degradează performanța generală.

Să înțelegem programarea dinamică printr-un exemplu.

 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)>