Динамічне програмування — це техніка, яка розбиває проблеми на підпроблеми та зберігає результат для майбутніх цілей, щоб нам не потрібно було знову обчислювати результат. Підпроблеми, оптимізовані для оптимізації загального рішення, відомі як властивість оптимальної підструктури. Основним використанням динамічного програмування є вирішення задач оптимізації. Тут проблеми оптимізації означають те, що ми намагаємося знайти мінімальне або максимальне рішення проблеми. Динамічне програмування гарантує знаходження оптимального рішення задачі, якщо воно існує.
Визначення динамічного програмування говорить, що це техніка для розв’язання складної проблеми, яка спочатку розбивається на набір простіших підзадач, розв’язується одна підпроблема лише один раз, а потім зберігається їх рішення, щоб уникнути повторюваних обчислень.
Розберемо цей підхід на прикладі.
Розглянемо приклад ряду Фібоначчі. Наступний ряд є рядом Фібоначчі:
нарізка java
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Числа в наведених вище рядах не обчислюються випадковим чином. Математично ми могли б записати кожен із термінів за допомогою наведеної нижче формули:
F(n) = F(n-1) + F(n-2),
З базовими значеннями F(0) = 0 і F(1) = 1. Щоб обчислити інші числа, ми дотримуємося наведеного вище співвідношення. Наприклад, F(2) є сумою f(0) і f(1), що дорівнює 1.
Як ми можемо обчислити F(20)?
Член F(20) буде обчислено за допомогою n-ї формули ряду Фібоначчі. На малюнку нижче показано, як обчислюється F(20).
порівняльний рядок у java
Як ми бачимо на малюнку вище, F(20) обчислюється як сума F(19) і F(18). У підході динамічного програмування ми намагаємося розділити проблему на подібні підпроблеми. Ми дотримуємося цього підходу в наведеному вище випадку, коли F(20) у подібні підпроблеми, тобто F(19) і F(18). Якщо ми нагадаємо визначення динамічного програмування, воно говорить, що подібна підпроблема не повинна обчислюватися більше одного разу. Тим не менш, у наведеному вище випадку підзадача обчислюється двічі. У наведеному вище прикладі F(18) обчислюється двічі; аналогічно, F(17) також обчислюється двічі. Однак ця техніка є досить корисною, оскільки вона вирішує подібні підпроблеми, але ми повинні бути обережними під час зберігання результатів, тому що ми не спеціалізуємося на зберіганні результату, який ми обчислили один раз, тоді це може призвести до марної витрати ресурсів.
У наведеному вище прикладі, якщо ми обчислюємо F(18) у правому піддереві, це призводить до надзвичайного використання ресурсів і зниження загальної продуктивності.
Рішення вищевказаної проблеми полягає в тому, щоб зберегти обчислені результати в масиві. Спочатку ми обчислюємо F(16) і F(17) і зберігаємо їхні значення в масиві. F(18) обчислюється шляхом підсумовування значень F(17) і F(16), які вже збережено в масиві. Обчислене значення F(18) зберігається в масиві. Значення F(19) обчислюється за допомогою суми F(18) і F(17), і їх значення вже збережено в масиві. Обчислене значення F(19) зберігається в масиві. Значення F(20) можна обчислити додаванням значень F(19) і F(18), і значення обох F(19) і F(18) зберігаються в масиві. Остаточне обчислене значення F(20) зберігається в масиві.
Як працює підхід динамічного програмування?
Нижче наведено кроки динамічного програмування:
- Він розбиває складну проблему на простіші підпроблеми.
- Він знаходить оптимальне рішення цих підпроблем.
- У ньому зберігаються результати підзадач (запам'ятовування). Процес збереження результатів підзадач відомий як запам'ятовування.
- Він повторно використовує їх, щоб одна і та ж підпроблема обчислювалася кілька разів.
- Нарешті обчисліть результат складної задачі.
Наведені вище п’ять кроків є основними для динамічного програмування. Динамічне програмування застосовне, що має такі властивості, як:
python новий рядок
Ті проблеми, які мають перекриваючі підпроблеми та оптимальні підструктури. Тут оптимальна підструктура означає, що розв’язок задач оптимізації може бути отриманий шляхом простого поєднання оптимального розв’язку всіх підзадач.
У випадку динамічного програмування просторова складність буде збільшена, оскільки ми зберігаємо проміжні результати, але часова складність буде зменшена.
Підходи динамічного програмування
Існує два підходи до динамічного програмування:
- Підхід зверху вниз
- Підхід «знизу вверх».
Підхід зверху вниз
Підхід «зверху вниз» застосовує техніку запам’ятовування, а підхід «знизу вгору» — метод таблиць. Тут запам'ятовування дорівнює сумі рекурсії та кешування. Рекурсія означає виклик самої функції, тоді як кешування означає збереження проміжних результатів.
Переваги
- Це дуже легко зрозуміти і реалізувати.
- Він вирішує підпроблеми лише тоді, коли це потрібно.
- Його легко налагодити.
Недоліки
підручник ssis
Він використовує техніку рекурсії, яка займає більше пам’яті в стеку викликів. Іноді, коли рекурсія надто глибока, виникає стан переповнення стека.
Він займає більше пам'яті, що погіршує загальну продуктивність.
Давайте розберемося в динамічному програмуванні на прикладі.
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)>