La programació dinàmica és una tècnica que divideix els problemes en subproblemes i guarda el resultat per a propòsits futurs de manera que no cal que tornem a calcular el resultat. Els subproblemes estan optimitzats per optimitzar la solució global que es coneix com a propietat de subestructura òptima. L'ús principal de la programació dinàmica és resoldre problemes d'optimització. Aquí, els problemes d'optimització volen dir que quan estem intentant trobar la solució mínima o màxima d'un problema. La programació dinàmica garanteix trobar la solució òptima d'un problema si la solució existeix.

La definició de programació dinàmica diu que és una tècnica per resoldre un problema complex desglossant primer una col·lecció de subproblemes més simples, resolent cada subproblema només una vegada i després emmagatzemant les seves solucions per evitar càlculs repetitius.

Entenem aquest enfocament a través d'un exemple.

Considereu un exemple de la sèrie de Fibonacci. La sèrie següent és la sèrie de Fibonacci:

javac no es reconeix

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

Els nombres de la sèrie anterior no es calculen aleatòriament. Matemàticament, podríem escriure cadascun dels termes utilitzant la fórmula següent:

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

Amb els valors base F(0) = 0, i F(1) = 1. Per calcular els altres nombres, seguim la relació anterior. Per exemple, F(2) és la suma f(0) i f(1), que és igual a 1.

Com podem calcular F(20)?

El terme F(20) es calcularà utilitzant la fórmula enèsima de la sèrie de Fibonacci. La figura següent mostra com es calcula F(20).

introduïu el maneig d'excepcions de Java

Com podem observar a la figura anterior que F(20) es calcula com la suma de F(19) i F(18). En l'enfocament de programació dinàmica, intentem dividir el problema en subproblemes similars. Seguim aquest enfocament en el cas anterior on F(20) en els subproblemes similars, és a dir, F(19) i F(18). Si recapitulem la definició de programació dinàmica que diu que el subproblema similar no s'ha de calcular més d'una vegada. Tot i així, en el cas anterior, el subproblema es calcula dues vegades. A l'exemple anterior, F(18) es calcula dues vegades; de la mateixa manera, F(17) també es calcula dues vegades. Tanmateix, aquesta tècnica és força útil, ja que resol els subproblemes similars, però hem de ser cautelosos a l'hora d'emmagatzemar els resultats perquè no som especials a l'hora d'emmagatzemar el resultat que hem calculat una vegada, llavors pot provocar un malbaratament de recursos.

A l'exemple anterior, si calculem la F(18) al subarbre correcte, això comporta un ús enorme de recursos i disminueix el rendiment global.

La solució al problema anterior és desar els resultats calculats en una matriu. Primer, calculem F(16) i F(17) i desem els seus valors en una matriu. La F(18) es calcula sumant els valors de F(17) i F(16), que ja estan desats en una matriu. El valor calculat de F(18) es desa en una matriu. El valor de F(19) es calcula utilitzant la suma de F(18) i F(17), i els seus valors ja estan desats en una matriu. El valor calculat de F(19) s'emmagatzema en una matriu. El valor de F(20) es pot calcular sumant els valors de F(19) i F(18), i els valors de F(19) i F(18) s'emmagatzemen en una matriu. El valor calculat final de F(20) s'emmagatzema en una matriu.

Com funciona l'enfocament de programació dinàmica?

Els següents són els passos que segueix la programació dinàmica:

• Desglossa el problema complex en subproblemes més simples.
• Troba la solució òptima a aquests subproblemes.
• Emmagatzema els resultats dels subproblemes (memoització). El procés d'emmagatzemar els resultats dels subproblemes es coneix com a memorització.
• Els reutilitza perquè el mateix subproblema es calculi més d'una vegada.
• Finalment, calculeu el resultat del problema complex.

Els cinc passos anteriors són els passos bàsics per a la programació dinàmica. És aplicable la programació dinàmica que tingui propietats com:

variable bash

Aquells problemes que tenen subproblemes superposats i subestructures òptimes. Aquí, la subestructura òptima significa que la solució dels problemes d'optimització es pot obtenir simplement combinant la solució òptima de tots els subproblemes.

En el cas de la programació dinàmica, la complexitat espacial augmentaria a mesura que anem emmagatzemant els resultats intermedis, però la complexitat temporal es reduiria.

Enfocaments de la programació dinàmica

Hi ha dos enfocaments per a la programació dinàmica:

• Enfocament de dalt a baix
• Enfocament de baix a dalt

Enfocament de dalt a baix

L'enfocament de dalt a baix segueix la tècnica de memorització, mentre que l'enfocament de baix a dalt segueix el mètode de tabulació. Aquí la memorització és igual a la suma de recursivitat i memòria cau. La recursència significa cridar la funció en si, mentre que la memòria cau significa emmagatzemar els resultats intermedis.

rebaixa amb imatges

Avantatges

• És molt fàcil d'entendre i implementar.
• Soluciona els subproblemes només quan és necessari.
• És fàcil de depurar.

Desavantatges

Utilitza la tècnica de recursivitat que ocupa més memòria a la pila de trucades. De vegades, quan la recursivitat és massa profunda, es produirà la condició de desbordament de la pila.

Ocupa més memòria que degrada el rendiment general.

Entenem la programació dinàmica a través d'un exemple.

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