eolymp

Динамічне програмування. Базові поняття.

   Задача 1. Новий Лабіринт Амбера

   Ідея розв’язання: Зрозуміло, що в першу комірку згідно умови ми потрапити не можемо, тому після зчитування вхідних даних занесемо до неї 0, не залежно від того, що нам пропонується для неї при зчитуванні вхідних даних, а у другу та третю ми можемо потрапити єдиним чином з початкової нульової комірки. Для всіх інших комірок у нас є вибір: потрапити до неї або з комірки під номером i–2, або з комірки під номером  i–3. Вибирати, звичайно, будемо ту, де перед цим вже є більша сума. Схематично це можна зобразити так (на прикладі з умови задачі):

Номери комірок

0

1

2

3

4

5

0

1000

2

3

1

3

Вміст комірок

    Замінимо вміст комірки 1 і починаючи з четвертої комірки, починаємо займатись вирішенням питання, звідки ж вигідніше у неї потрапити: з комірки a[i–2] чи a[i–3]?

awp_dp01

   Звичайно, що вигідніше в комірку під номером 4 потрапити з комірки під номером 2 (з індексом i–2), так як там вже є 2 монетки і сума буде 3, а в комірці під номером 1 (з індексом i–3) вже накопичено 0 монеток, і сума буде 1, що є не вигідним. Не заводячи додаткового масиву, будемо зберігати у цій поточній розглядуваній комірці знайдену суму, яку формально можемо описати так:

awp_dp012

   Тоді при переході до вибору стратегії переходу у наступній комірці під номером 5, наш вибір зміниться на наступний:

awp_dp02

   Звичайно, що і в цю комірку вигідніше потрапити з комірки з індексом i–2, де збергіається монет на одиницю більше.  В результаті наша таблиця буде мати вигляд:

Номери комірок

0

1

2

3

4

5

0

0

2

3

3

6

Вміст комірок

   В результаті у нас у кінцевій (N-тій) комірці завжди буде знаходитись відповідь до задачі.

   Описаний вище підхід лежить в основі динамічного програмування. В основу принципу динамічного програмування покладено наступну просту стратегію оптимальної політики, вказану Р.Беллманом і названу ним принципом оптимальності: „Саме оптимальній політиці притамана та властивість, що якими б не були початковий стан і перший розвязок, наступні розвязки складають оптимальну політику відносно початкового стану, отриманого в результаті першого розвязку.”

   Задача 2. Сходинки

   Ідея розвязання: Розв`язок даної задачі трохи відрізняється від попередньої лише тим, що на кожну поточну розглядувану сходинку ми можемо потрапити вже маючи вибір не з 2-х можливих, а з K попередніх сходинок. Цей підхід легко реалізується при допомозі додаткового циклу. Щоб не змінювати логіку пошуку попередньої програми задамо масив, використовуючи ту особливість мови паскаль, що нумерувати масив можна починаючи з довільного індексу. 

   Підказка: масив чисел, що зберігаються на сходинках, слід оголосити як a : array[-1000..1001] of longint;

   Задача 3. Одиниці

   Ідея розвязання: Зрозуміло, що для того, щоб отримати число 1 достатньо просто написати одну одиницю, а число 2 отримується шляхом додавання двох одиниць. Подальша логіка така: ми можемо довільне наступне число знайти, додавши до попереднього одну одиницю (a[k] = a[k-1] + 1) - це і є перше наближення оптимального розв'язку. Після цього пробуємо число k розкласти на два множники, і якщо це вдалось, то сума одиниць, які входять у кажен з співмножників перевіряється з поточним оптимальним значенням a[k], якщо знайдене число виявиться меншим, відповідно принймаємо його за оптимальне. Шукати роклади достатньо до sqrt(k).

   Задача 4. Paint2D

   Ідея розв`язання: Ідею розв`язання даної задачі разберемо більш детально.

(Далі буде)