La programmazione dinamica è una tecnica che suddivide i problemi in sottoproblemi e salva il risultato per scopi futuri in modo che non sia necessario calcolarlo nuovamente. I sottoproblemi sono ottimizzati per ottimizzare la soluzione complessiva, nota come proprietà della sottostruttura ottimale. L'uso principale della programmazione dinamica è risolvere problemi di ottimizzazione. In questo caso, problemi di ottimizzazione significano quando stiamo cercando di trovare la soluzione minima o massima di un problema. La programmazione dinamica garantisce di trovare la soluzione ottimale di un problema se la soluzione esiste.
La definizione di programmazione dinamica afferma che si tratta di una tecnica per risolvere un problema complesso suddividendosi prima in una raccolta di sottoproblemi più semplici, risolvendo ciascun sottoproblema una sola volta e quindi memorizzando le relative soluzioni per evitare calcoli ripetitivi.
Comprendiamo questo approccio attraverso un esempio.
Consideriamo un esempio della serie di Fibonacci. La seguente serie è la serie di Fibonacci:
idea intelligente vs eclissi
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
I numeri nelle serie precedenti non sono calcolati in modo casuale. Matematicamente, potremmo scrivere ciascuno dei termini utilizzando la formula seguente:
F(n) = F(n-1) + F(n-2),
Con i valori di base F(0) = 0 e F(1) = 1. Per calcolare gli altri numeri, seguiamo la relazione sopra. Ad esempio, F(2) è la somma f(0) E f(1), che è uguale a 1.
Come possiamo calcolare F(20)?
Il termine F(20) verrà calcolato utilizzando l'ennesima formula della serie di Fibonacci. La figura seguente mostra come viene calcolato F(20).
dimensione del carattere in lattice
Come possiamo osservare nella figura sopra, F(20) è calcolato come la somma di F(19) e F(18). Nell'approccio di programmazione dinamica, proviamo a dividere il problema in sottoproblemi simili. Stiamo seguendo questo approccio nel caso precedente in cui F(20) nei sottoproblemi simili, ovvero F(19) e F(18). Se ricapitoliamo la definizione di programmazione dinamica, si dice che il sottoproblema simile non dovrebbe essere calcolato più di una volta. Tuttavia, nel caso precedente, il sottoproblema viene calcolato due volte. Nell'esempio precedente, F(18) viene calcolato due volte; analogamente, anche F(17) viene calcolato due volte. Tuttavia, questa tecnica è abbastanza utile in quanto risolve sottoproblemi simili, ma dobbiamo essere cauti durante la memorizzazione dei risultati perché non siamo particolari nel memorizzare il risultato che abbiamo calcolato una volta, quindi può portare a uno spreco di risorse.
Nell'esempio precedente, se calcoliamo F(18) nel sottoalbero di destra, ciò comporta un utilizzo enorme delle risorse e una diminuzione delle prestazioni complessive.
La soluzione al problema precedente è salvare i risultati calcolati in un array. Per prima cosa calcoliamo F(16) e F(17) e salviamo i loro valori in un array. F(18) viene calcolato sommando i valori di F(17) e F(16), che sono già salvati in un array. Il valore calcolato di F(18) viene salvato in un array. Il valore di F(19) viene calcolato utilizzando la somma di F(18) e F(17) e i relativi valori sono già salvati in un array. Il valore calcolato di F(19) viene memorizzato in un array. Il valore di F(20) può essere calcolato sommando i valori di F(19) e F(18) e i valori di F(19) e F(18) vengono memorizzati in un array. Il valore calcolato finale di F(20) viene memorizzato in un array.
Come funziona l'approccio di programmazione dinamica?
Di seguito sono riportati i passaggi che segue la programmazione dinamica:
- Suddivide il problema complesso in sottoproblemi più semplici.
- Trova la soluzione ottimale a questi sottoproblemi.
- Memorizza i risultati dei sottoproblemi (memoizzazione). Il processo di memorizzazione dei risultati dei sottoproblemi è noto come memorizzazione.
- Li riutilizza in modo che lo stesso sottoproblema venga calcolato più di una volta.
- Infine, calcola il risultato del problema complesso.
I cinque passaggi precedenti sono i passaggi fondamentali per la programmazione dinamica. È applicabile la programmazione dinamica che ha proprietà come:
impostazione del percorso Python
Quei problemi che hanno sottoproblemi sovrapposti e sottostrutture ottimali. Qui, sottostruttura ottima significa che la soluzione dei problemi di ottimizzazione può essere ottenuta semplicemente combinando la soluzione ottima di tutti i sottoproblemi.
Nel caso della programmazione dinamica, la complessità spaziale aumenterebbe man mano che si memorizzano i risultati intermedi, ma la complessità temporale diminuirebbe.
Approcci di programmazione dinamica
Esistono due approcci alla programmazione dinamica:
- Approccio dall 'alto verso il basso
- Approccio dal basso verso l'alto
Approccio dall 'alto verso il basso
L'approccio top-down segue la tecnica di memorizzazione, mentre l'approccio bottom-up segue il metodo della tabulazione. Qui la memorizzazione è uguale alla somma di ricorsione e memorizzazione nella cache. La ricorsione significa chiamare la funzione stessa, mentre la memorizzazione nella cache significa memorizzare i risultati intermedi.
Vantaggi
- È molto facile da capire e implementare.
- Risolve i sottoproblemi solo quando è richiesto.
- È facile eseguire il debug.
Svantaggi
cm in piedi e pollici
Utilizza la tecnica di ricorsione che occupa più memoria nello stack di chiamate. A volte, quando la ricorsione è troppo profonda, si verifica una condizione di overflow dello stack.
Occupa più memoria, il che peggiora le prestazioni complessive.
Comprendiamo la programmazione dinamica attraverso un esempio.
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)>