Dynamisch programmeren is een techniek die de problemen in subproblemen opsplitst en het resultaat opslaat voor toekomstige doeleinden, zodat we het resultaat niet opnieuw hoeven te berekenen. De deelproblemen worden geoptimaliseerd om de algehele oplossing te optimaliseren. Dit wordt de optimale onderbouweigenschap genoemd. Het belangrijkste gebruik van dynamisch programmeren is het oplossen van optimalisatieproblemen. Optimalisatieproblemen betekenen hier dat wanneer we proberen de minimale of maximale oplossing van een probleem te vinden. De dynamische programmering garandeert het vinden van de optimale oplossing van een probleem als de oplossing bestaat.
De definitie van dynamisch programmeren zegt dat het een techniek is om een complex probleem op te lossen door eerst een verzameling eenvoudiger deelproblemen op te splitsen, elk deelprobleem slechts één keer op te lossen en vervolgens de oplossingen ervan op te slaan om repetitieve berekeningen te voorkomen.
Laten we deze aanpak begrijpen aan de hand van een voorbeeld.
Beschouw een voorbeeld van de Fibonacci-reeks. De volgende reeks is de Fibonacci-reeks:
converteer boolean naar string
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
De getallen in de bovenstaande reeksen zijn niet willekeurig berekend. Wiskundig gezien zouden we elk van de termen kunnen schrijven met behulp van de onderstaande formule:
F(n) = F(n-1) + F(n-2),
Met de basiswaarden F(0) = 0, en F(1) = 1. Om de overige getallen te berekenen, volgen we bovenstaande relatie. F(2) is bijvoorbeeld de som f(0) En f(1), wat gelijk is aan 1.
Hoe kunnen we F(20) berekenen?
De F(20)-term wordt berekend met behulp van de n-de formule van de Fibonacci-reeks. De onderstaande afbeelding laat zien hoe F(20) wordt berekend.
prioriteit wachtrij java
Zoals we in de bovenstaande figuur kunnen zien, wordt F(20) berekend als de som van F(19) en F(18). Bij de dynamische programmeerbenadering proberen we het probleem op te delen in soortgelijke deelproblemen. We volgen deze aanpak in het bovenstaande geval waarin F(20) in de vergelijkbare subproblemen werkt, dat wil zeggen F(19) en F(18). Als we de definitie van dynamisch programmeren samenvatten, staat er dat het soortgelijke deelprobleem niet meer dan één keer mag worden berekend. In het bovenstaande geval wordt het deelprobleem echter tweemaal berekend. In het bovenstaande voorbeeld wordt F(18) twee keer berekend; op dezelfde manier wordt F(17) ook tweemaal berekend. Deze techniek is echter behoorlijk nuttig omdat het vergelijkbare deelproblemen oplost, maar we moeten voorzichtig zijn bij het opslaan van de resultaten, omdat we niet bijzonder zijn in het opslaan van het resultaat dat we eenmaal hebben berekend. Dit kan dan leiden tot verspilling van middelen.
Als we in het bovenstaande voorbeeld de F(18) in de rechter subboom berekenen, leidt dit tot een enorm gebruik van hulpbronnen en neemt de algehele prestatie af.
De oplossing voor het bovenstaande probleem is om de berekende resultaten in een array op te slaan. Eerst berekenen we F(16) en F(17) en slaan hun waarden op in een array. De F(18) wordt berekend door de waarden van F(17) en F(16) op te tellen, die al in een array zijn opgeslagen. De berekende waarde van F(18) wordt opgeslagen in een array. De waarde van F(19) wordt berekend met behulp van de som van F(18) en F(17), en hun waarden zijn al opgeslagen in een array. De berekende waarde van F(19) wordt opgeslagen in een array. De waarde van F(20) kan worden berekend door de waarden van F(19) en F(18) op te tellen, en de waarden van zowel F(19) als F(18) worden opgeslagen in een array. De uiteindelijke berekende waarde van F(20) wordt opgeslagen in een array.
Hoe werkt de dynamische programmeeraanpak?
Hieronder volgen de stappen die de dynamische programmering volgt:
- Het verdeelt het complexe probleem in eenvoudiger deelproblemen.
- Het vindt de optimale oplossing voor deze deelproblemen.
- Het slaat de resultaten van deelproblemen op (memoisatie). Het proces van het opslaan van de resultaten van deelproblemen staat bekend als memoriseren.
- Het hergebruikt ze zodat hetzelfde deelprobleem meerdere keren wordt berekend.
- Bereken ten slotte het resultaat van het complexe probleem.
De bovenstaande vijf stappen zijn de basisstappen voor dynamisch programmeren. De dynamische programmering is van toepassing met eigenschappen zoals:
wat zijn de afmetingen van mijn computerscherm
Die problemen die overlappende subproblemen en optimale substructuren hebben. Hier betekent optimale substructuur dat de oplossing van optimalisatieproblemen kan worden verkregen door simpelweg de optimale oplossing van alle subproblemen te combineren.
In het geval van dynamisch programmeren zou de ruimtecomplexiteit toenemen naarmate we de tussenresultaten opslaan, maar zou de tijdcomplexiteit afnemen.
Benaderingen van dynamisch programmeren
Er zijn twee benaderingen van dynamisch programmeren:
aaneenschakeling van Java-tekenreeks
- Top-down benadering
- Bottom-up benadering
Top-down benadering
De top-down benadering volgt de memorisatietechniek, terwijl de bottom-up benadering de tabelleringsmethode volgt. Hier is het onthouden gelijk aan de som van recursie en caching. Recursie betekent het aanroepen van de functie zelf, terwijl caching het opslaan van de tussenresultaten betekent.
Voordelen
- Het is heel gemakkelijk te begrijpen en te implementeren.
- Het lost de deelproblemen alleen op als dat nodig is.
- Het is gemakkelijk te debuggen.
Nadelen
Het maakt gebruik van de recursietechniek die meer geheugen in de call-stack in beslag neemt. Soms, als de recursie te diep is, zal de stack-overflow-toestand optreden.
Het neemt meer geheugen in beslag, wat de algehele prestaties verslechtert.
Laten we dynamisch programmeren begrijpen aan de hand van een voorbeeld.
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)>