Dynamisk programmering är en teknik som delar upp problemen i delproblem, och sparar resultatet för framtida ändamål så att vi inte behöver beräkna resultatet igen. Delproblemen är optimerade för att optimera den övergripande lösningen kallas optimal underbyggnadsegenskap. Den huvudsakliga användningen av dynamisk programmering är att lösa optimeringsproblem. Här betyder optimeringsproblem att när vi försöker ta reda på minimum eller maximal lösning av ett problem. Den dynamiska programmeringen garanterar att hitta den optimala lösningen på ett problem om lösningen finns.

Definitionen av dynamisk programmering säger att det är en teknik för att lösa ett komplext problem genom att först bryta in i en samling enklare delproblem, lösa varje delproblem bara en gång och sedan lagra deras lösningar för att undvika repetitiva beräkningar.

Låt oss förstå detta tillvägagångssätt genom ett exempel.

Tänk på ett exempel på Fibonacci-serien. Följande serie är Fibonacci-serien:

prime ingen kod i java

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

Siffrorna i ovanstående serie är inte slumpmässigt beräknade. Matematiskt kan vi skriva var och en av termerna med följande formel:

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

Med basvärdena F(0) = 0, och F(1) = 1. För att beräkna de andra talen följer vi ovanstående samband. Till exempel är F(2) summan f(0) och f(1), som är lika med 1.

Hur kan vi beräkna F(20)?

F(20)-termen kommer att beräknas med den n:te formeln i Fibonacci-serien. Figuren nedan visar hur F(20) beräknas.

lär dig noggrannhetspoäng

Som vi kan observera i figuren ovan att F(20) beräknas som summan av F(19) och F(18). I det dynamiska programmeringssättet försöker vi dela upp problemet i liknande delproblem. Vi följer detta tillvägagångssätt i ovanstående fall där F(20) in i liknande delproblem, dvs F(19) och F(18). Om vi ​​sammanfattar definitionen av dynamisk programmering så står det att liknande delproblem inte bör beräknas mer än en gång. Ändå, i ovanstående fall, beräknas delproblemet två gånger. I exemplet ovan beräknas F(18) två gånger; på liknande sätt beräknas även F(17) två gånger. Den här tekniken är dock ganska användbar eftersom den löser liknande delproblem, men vi måste vara försiktiga när vi lagrar resultaten eftersom vi inte är särskilt noga med att lagra resultatet som vi har beräknat en gång, då kan det leda till slöseri med resurser.

I exemplet ovan, om vi beräknar F(18) i det högra underträdet, leder det till en enorm resursanvändning och minskar den totala prestandan.

Lösningen på ovanstående problem är att spara de beräknade resultaten i en array. Först beräknar vi F(16) och F(17) och sparar deras värden i en array. F(18) beräknas genom att summera värdena för F(17) och F(16), som redan är sparade i en array. Det beräknade värdet på F(18) sparas i en array. Värdet på F(19) beräknas med hjälp av summan av F(18) och F(17), och deras värden är redan sparade i en array. Det beräknade värdet på F(19) lagras i en array. Värdet på F(20) kan beräknas genom att addera värdena för F(19) och F(18), och värdena för både F(19) och F(18) lagras i en array. Det slutliga beräknade värdet på F(20) lagras i en array.

Hur fungerar det dynamiska programmeringssättet?

Följande är stegen som den dynamiska programmeringen följer:

• Det bryter ner det komplexa problemet i enklare delproblem.
• Den hittar den optimala lösningen på dessa delproblem.
• Den lagrar resultaten av delproblem (memoisering). Processen att lagra resultaten av delproblem kallas memorering.
• Den återanvänder dem så att samma delproblem beräknas mer än en gång.
• Beräkna slutligen resultatet av det komplexa problemet.

Ovanstående fem steg är de grundläggande stegen för dynamisk programmering. Den dynamiska programmeringen är tillämplig som har egenskaper som:

java int till char

De problem som har överlappande delproblem och optimala understrukturer. Här innebär optimal understruktur att lösningen av optimeringsproblem kan erhållas genom att helt enkelt kombinera den optimala lösningen av alla delproblemen.

I fallet med dynamisk programmering skulle rymdkomplexiteten ökas när vi lagrar mellanresultaten, men tidskomplexiteten skulle minska.

Tillvägagångssätt för dynamisk programmering

Det finns två metoder för dynamisk programmering:

arraylist och länkad lista

• Uppifrån och ner tillvägagångssätt
• Bottom-up-strategi

Uppifrån och ner tillvägagångssätt

Top-down-metoden följer memoreringstekniken, medan bottom-up-metoden följer tabuleringsmetoden. Här är memorering lika med summan av rekursion och cachning. Rekursion innebär att anropa själva funktionen, medan cachning innebär lagring av mellanresultaten.

Fördelar

• Det är väldigt lätt att förstå och implementera.
• Det löser delproblemen endast när det krävs.
• Det är lätt att felsöka.

Nackdelar

Den använder rekursionstekniken som upptar mer minne i anropsstacken. Ibland när rekursionen är för djup, kommer stackoverflow-tillståndet att inträffa.

Det upptar mer minne som försämrar den övergripande prestandan.

Låt oss förstå dynamisk programmering genom ett exempel.

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