Dinaminis programavimas yra technika, kuri suskaido problemas į subproblemas ir išsaugo rezultatą ateities tikslams, kad mums nereikėtų skaičiuoti rezultato dar kartą. Subproblemos yra optimizuotos, kad būtų optimizuotas bendras sprendimas, žinomas kaip optimali pagrindo savybė. Pagrindinis dinaminio programavimo panaudojimas yra optimizavimo problemų sprendimas. Čia optimizavimo problemos reiškia, kad mes bandome išsiaiškinti minimalų arba maksimalų problemos sprendimą. Dinaminis programavimas garantuoja optimalų problemos sprendimą, jei sprendimas egzistuoja.
Dinaminio programavimo apibrėžimas sako, kad tai sudėtingos problemos sprendimo technika, pirmiausia suskirstant į paprastesnių subproblemų rinkinį, išsprendžiant kiekvieną poproblemą tik vieną kartą ir išsaugont jų sprendimus, kad būtų išvengta pasikartojančių skaičiavimų.
Supraskime šį požiūrį per pavyzdį.
Apsvarstykite Fibonačio serijos pavyzdį. Ši serija yra Fibonacci serija:
rihannos amžius
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Aukščiau pateiktų serijų skaičiai nėra atsitiktinai apskaičiuoti. Matematiškai kiekvieną terminą galėtume parašyti naudodami toliau pateiktą formulę:
F(n) = F(n-1) + F(n-2),
Su bazinėmis reikšmėmis F(0) = 0 ir F(1) = 1. Norėdami apskaičiuoti kitus skaičius, vadovaujamės aukščiau pateiktu ryšiu. Pavyzdžiui, F(2) yra suma f(0) ir f(1), kuris lygus 1.
Kaip galime apskaičiuoti F(20)?
F(20) narys bus apskaičiuojamas naudojant n-ąją Fibonačio serijos formulę. Žemiau pateiktame paveikslėlyje parodyta, kaip apskaičiuojamas F(20).
pridėti prie masyvo java
Kaip matome aukščiau esančiame paveikslėlyje, F(20) apskaičiuojamas kaip F(19) ir F(18) suma. Dinaminio programavimo metodu bandome padalinti problemą į panašias subproblemas. Mes laikomės šio požiūrio aukščiau pateiktu atveju, kai F (20) į panašias subproblemas, ty F (19) ir F (18). Jei apibendrinsime dinaminio programavimo apibrėžimą, jis sako, kad panaši antrinė problema neturėtų būti skaičiuojama daugiau nei vieną kartą. Visgi aukščiau nurodytu atveju subproblema skaičiuojama du kartus. Aukščiau pateiktame pavyzdyje F(18) apskaičiuojamas du kartus; taip pat F(17) taip pat apskaičiuojamas du kartus. Tačiau šis metodas yra gana naudingas, nes išsprendžia panašias antrines problemas, tačiau turime būti atsargūs saugant rezultatus, nes nesame ypatingai saugoję vieną kartą apskaičiuotą rezultatą, todėl gali būti švaistomi ištekliai.
Aukščiau pateiktame pavyzdyje, jei apskaičiuojame F(18) dešiniajame pomedyje, tai lemia milžinišką išteklių naudojimą ir sumažina bendrą našumą.
Aukščiau pateiktos problemos sprendimas yra įrašyti apskaičiuotus rezultatus masyve. Pirmiausia apskaičiuojame F(16) ir F(17) ir išsaugome jų reikšmes masyve. F(18) apskaičiuojamas sudedant F(17) ir F(16) reikšmes, kurios jau yra išsaugotos masyve. Apskaičiuota F(18) reikšmė išsaugoma masyve. F(19) reikšmė apskaičiuojama naudojant F(18) ir F(17) sumą, o jų reikšmės jau išsaugotos masyve. Apskaičiuota F(19) reikšmė saugoma masyve. F(20) reikšmę galima apskaičiuoti sudėjus F(19) ir F(18) reikšmes, o F(19) ir F(18) reikšmės saugomos masyve. Galutinė apskaičiuota F(20) reikšmė saugoma masyve.
Kaip veikia dinaminio programavimo metodas?
Toliau pateikiami žingsniai, kuriuos atlieka dinaminis programavimas:
- Jis suskaido sudėtingą problemą į paprastesnes dalis.
- Jis randa optimalų šių papildomų problemų sprendimą.
- Jame saugomi subproblemų rezultatai (atmintinė). Subproblemų rezultatų saugojimo procesas žinomas kaip įsiminimas.
- Jis juos naudoja pakartotinai, kad ta pati antrinė problema būtų apskaičiuojama daugiau nei vieną kartą.
- Galiausiai apskaičiuokite sudėtingos problemos rezultatą.
Pirmiau minėti penki veiksmai yra pagrindiniai dinaminio programavimo žingsniai. Taikomas dinaminis programavimas, turintis tokias savybes kaip:
java metodai
Tos problemos, kurios turi persidengiančių poproblemų ir optimalių postruktūrų. Čia optimali postruktūra reiškia, kad optimizavimo uždavinių sprendimą galima gauti tiesiog sujungus optimalų visų subproblemų sprendimą.
Dinaminio programavimo atveju erdvės sudėtingumas padidėtų, nes saugome tarpinius rezultatus, bet sumažėtų laiko sudėtingumas.
Dinaminio programavimo požiūriai
Yra du dinaminio programavimo būdai:
primityvūs duomenų tipai Java
- „Iš viršaus į apačią“ metodas
- „Iš apačios į viršų“ metodas
„Iš viršaus į apačią“ metodas
„Iš viršaus į apačią“ taikomas įsiminimo metodas, o metodas „iš apačios į viršų“ – lentelės sudarymo metodu. Čia įsiminimas yra lygus rekursijos ir talpyklos sumai. Rekursija reiškia pačios funkcijos iškvietimą, o talpyklos saugojimas reiškia tarpinių rezultatų saugojimą.
Privalumai
- Tai labai lengva suprasti ir įgyvendinti.
- Jis išsprendžia subproblemas tik tada, kai to reikia.
- Tai lengva derinti.
Trūkumai
Jis naudoja rekursijos techniką, kuri skambučių krūvoje užima daugiau atminties. Kartais, kai rekursija yra per gili, įvyksta dėklo perpildymo sąlyga.
Tai užima daugiau atminties, o tai sumažina bendrą našumą.
Supraskime dinaminį programavimą per pavyzdį.
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)>