Programowanie dynamiczne to technika, która dzieli problemy na podproblemy i zapisuje wynik do przyszłych celów, dzięki czemu nie trzeba ponownie obliczać wyniku. Podproblemy są optymalizowane w celu optymalizacji ogólnego rozwiązania, co jest znane jako optymalna właściwość podstruktury. Głównym zastosowaniem programowania dynamicznego jest rozwiązywanie problemów optymalizacyjnych. Tutaj problemy optymalizacyjne oznaczają, że staramy się znaleźć minimalne lub maksymalne rozwiązanie problemu. Programowanie dynamiczne gwarantuje znalezienie optymalnego rozwiązania problemu, jeśli takie rozwiązanie istnieje.

Definicja programowania dynamicznego mówi, że jest to technika rozwiązywania złożonego problemu polegająca na rozbiciu najpierw zbioru prostszych podproblemów, rozwiązywaniu każdego podproblemu tylko raz, a następnie przechowywaniu ich rozwiązań, aby uniknąć powtarzających się obliczeń.

Rozumiemy to podejście na przykładzie.

Rozważmy przykład ciągu Fibonacciego. Poniższy szereg to ciąg Fibonacciego:

sprawdzenie Java ma wartość null

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

Liczby w powyższych seriach nie są obliczane losowo. Matematycznie każdy z terminów moglibyśmy zapisać za pomocą poniższego wzoru:

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

Przy wartościach podstawowych F(0) = 0 i F(1) = 1. Aby obliczyć pozostałe liczby, postępujemy zgodnie z powyższą zależnością. Na przykład F(2) jest sumą f(0) I f(1), co jest równe 1.

Jak możemy obliczyć F(20)?

Wyraz F(20) zostanie obliczony przy użyciu n-tego wzoru ciągu Fibonacciego. Poniższy rysunek pokazuje sposób obliczania F(20).

przycinanie alfa-beta

Jak widać na powyższym rysunku, F(20) oblicza się jako sumę F(19) i F(18). W podejściu do programowania dynamicznego staramy się podzielić problem na podobne podproblemy. Postępujemy zgodnie z tym podejściem w powyższym przypadku, gdzie F(20) rozbijamy na podobne podproblemy, tj. F(19) i F(18). Jeśli podsumujemy definicję programowania dynamicznego, która mówi, że podobnego podproblemu nie należy obliczać więcej niż raz. Jednak w powyższym przypadku podproblem jest obliczany dwukrotnie. W powyższym przykładzie F(18) oblicza się dwukrotnie; podobnie F(17) również oblicza się dwukrotnie. Jednak ta technika jest całkiem przydatna, ponieważ rozwiązuje podobne podproblemy, ale musimy zachować ostrożność podczas przechowywania wyników, ponieważ nie skupiamy się specjalnie na przechowywaniu wyniku, który obliczyliśmy raz, może to prowadzić do marnowania zasobów.

W powyższym przykładzie, jeśli obliczymy F(18) w prawym poddrzewie, prowadzi to do ogromnego zużycia zasobów i zmniejsza ogólną wydajność.

Rozwiązaniem powyższego problemu jest zapisanie obliczonych wyników w tablicy. Najpierw obliczamy F(16) i F(17) i zapisujemy ich wartości w tablicy. Wartość F(18) oblicza się, sumując wartości F(17) i F(16), które są już zapisane w tablicy. Obliczona wartość F(18) jest zapisywana w tablicy. Wartość F(19) jest obliczana na podstawie sumy F(18) i F(17), a ich wartości są już zapisane w tablicy. Obliczona wartość F(19) jest przechowywana w tablicy. Wartość F(20) można obliczyć, dodając wartości F(19) i F(18), a wartości F(19) i F(18) są przechowywane w tablicy. Ostateczna obliczona wartość F(20) jest przechowywana w tablicy.

Jak działa podejście do programowania dynamicznego?

Poniżej przedstawiono kroki, które wykonuje programowanie dynamiczne:

• Rozbija złożony problem na prostsze podproblemy.
• Znajduje optymalne rozwiązanie tych podproblemów.
• Przechowuje wyniki podproblemów (zapamiętywanie). Proces przechowywania wyników podproblemów nazywany jest zapamiętywaniem.
• Wykorzystuje je ponownie, dzięki czemu ten sam podproblem jest obliczany więcej niż raz.
• Na koniec oblicz wynik złożonego problemu.

Powyższe pięć kroków to podstawowe kroki programowania dynamicznego. Zastosowanie ma programowanie dynamiczne posiadające właściwości takie jak:

oprogramowanie systemowe

Problemy, które mają nakładające się podproblemy i optymalne podstruktury. Optymalna podstruktura oznacza tutaj, że rozwiązanie problemów optymalizacyjnych można uzyskać po prostu łącząc optymalne rozwiązania wszystkich podproblemów.

W przypadku programowania dynamicznego złożoność przestrzenna wzrosłaby w miarę przechowywania wyników pośrednich, ale złożoność czasowa uległaby zmniejszeniu.

Podejścia programowania dynamicznego

Istnieją dwa podejścia do programowania dynamicznego:

• Podejście odgórne
• Podejście oddolne

Podejście odgórne

Podejście odgórne opiera się na technice zapamiętywania, natomiast podejście oddolne opiera się na metodzie tabulacji. Tutaj zapamiętywanie jest równe sumie rekurencji i buforowania. Rekurencja oznacza wywołanie samej funkcji, podczas gdy buforowanie oznacza przechowywanie wyników pośrednich.

Zalety

czas trwania Javy

• Jest to bardzo łatwe do zrozumienia i wdrożenia.
• Rozwiązuje podproblemy tylko wtedy, gdy jest to wymagane.
• Jest łatwy do debugowania.

Niedogodności

Używa techniki rekurencji, która zajmuje więcej pamięci na stosie wywołań. Czasami, gdy rekurencja jest zbyt głęboka, wystąpi warunek przepełnienia stosu.

Zajmuje więcej pamięci, co pogarsza ogólną wydajność.

Przyjrzyjmy się programowaniu dynamicznemu na przykładzie.

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