Динамічне програмування для початківців


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Динамічне програмування – тема, якій в рунеті присвячено мало статей, тому ми вирішили нею зайнятися. У цій статті будуть розібрані класичні задачі на послідовність, одновимірну і двовимірну динаміку, буде дано обґрунтування розв’язанням і описані різні підходи до їх реалізації. Весь наведений в статті код написаний на Java.

Про що взагалі йдеться? Що таке динамічне програмування?

Динамічне програмування – метод розв’язання задачі шляхом її розбиття на декілька однакових підзадач, рекурентно пов’язаних між собою. Найпростішим прикладом будуть числа Фібоначчі – щоб обчислити деяке число в цій послідовності, нам треба спершу обчислити третє число, склавши перші два, потім четверте так само на основі другого і третього, і так далі (так, ми чули про замкнуту формулу).

Добре, як це використати?

Розв’язання задачі динамічним програмуванням повинне містити:

  • Залежність елементів динаміки один від одного. Така залежність може бути прямо дана в умові (так часто буває, якщо це задача на числові послідовності). Інакше Ви можете спробувати впізнати якийсь відомий числовий ряд (на зразок тих же чисел Фібоначчі), обчисливши перші декілька значень вручну. Якщо Вам зовсім не поталанило – доведеться думати
  • Значення початкових станів. У результаті довгого розбиття на підзадачі Вам необхідно звести функцію або до вже відомих значень (як у випадку з Фібоначчі – заздалегідь визначені перші два члени), або до задачі, що розв’язується елементарно.

І мені для розв’язання рекурсивний метод писати потрібно? Я чув, вони повільні.

Звичайно, не потрібно, є й інші підходи до реалізації динаміки. Розберемо їх на прикладі наступної задачі:

Обчислити n-й член послідовності, заданої формулами:
a2n = an ­+ an – 1,
a2n+1 = an – an – 1,
a0 = a1 = 1.

Ідея розв’язання

Тут нам дані й початкові стани (a0 = a1 = 1), і залежності. Єдина складність, яка може виникнути, – розуміння того, що 2n – умова парності числа, а 2n+1 – непарності. Іншими словами, нам треба перевіряти, чи парне число, і обчислювати його залежно від цього за різними формулами.

Рекурсивне розв’язання

Очевидна реалізація полягає в написанні наступного методу:

private static int f (int n){ if (n==0 || n==1) return 1; // Перевірка на початкове значення if (n%2==0){ //Перевірка на парність return f (n/2) +f (n/2-1); // Обчислюємо за формулою для парних індексів, // посилаючись на попередні значення }else{ return f ((n - 1)/2) - f ((n - 1)/2-1); // Обчислюємо за формулою для непарних //індексів, посилаючись на попередні значення }}

І вона відмінно працює, але є нюанси. Якщо ми захочемо обчислити f (12), то метод обчислюватиме суму f (6) +f (5). В той же час, f (6) =f (3) +f (2) і f (5) =f (2) - f (1), тобто значення f (2) ми обчислюватимемо двічі. Порятунок від цього є – мемоїзація (кешування значень).

Рекурсивне розв’язання з кешуванням значень

Для вже написаної функції f (int) кешування значень виглядатиме так:

private static HashMap<Integer, Integer> cache = new HashMap<Integer, Integer>();private static int fcashe (int n){ if (!cache.containsKey (n)){//Перевіряємо, чи знаходили ми це значення cache.put (n, f (n)); //Якщо ні, то знаходимо і записуємо в таблицю } return cache.get (n);}

Не занадто складно, погодьтеся? Це позбавляє від величезного числа операцій. Платите Ви за це зайвою витратою пам’яті.

Послідовне обчислення

Тепер повернемося до того, з чого розпочали – рекурсія працює повільно. Не занадто повільно, щоб це завдавало неприємностей у справжньому житті, але на змаганнях зі спортивного програмування кожна мілісекунда на рахунку.

Метод послідовного обчислення підходить, тільки якщо функція посилається винятково на елементи перед нею – це його основний, але не єдиний мінус. Наша задача цій умові задовольняє.

Суть методу полягає в наступному: ми створюємо масив на N елементів і послідовно заповнюємо його значеннями. Ви, напевно, вже здогадалися, що таким чином ми можемо обчислювати у тому числі ті значення, які для відповіді не потрібні. У значній частині задач на динаміку цей факт можна опустити, оскільки для відповіді часто бувають потрібні якраз усі значення. Наприклад, при пошуку найменшого шляху ми не можемо не обчислювати шлях до якоїсь точки, нам треба переглянути всі варіанти. В нашій задачі нам треба обчислювати приблизно log2(N) значень (на практиці більше), для 922337203685477580-го елемента (MaxLong/10) нам знадобиться 172 обчислення.

private static int f (int n){if (n<2) return 1; //Може, нам і обчислювати нічого не треба?int[] fs = int[n]; //Створюємо масив для значень
fs[0]=fs[1]=1; //Задаємо початкові состоянияfor (int i=2; i<n; i++){ if (i%2==0){ //Перевіряємо парність fs[i]=fs[i/2]+fs[i/2-1]; }else{ fs[i]=fs[(i - 1)/2]+fs[(i - 1)/2-1] }}return fs[n - 1];}

Ще одним мінусом такого підходу є порівняно велика витрата пам’яті.

Створення стека індексів

Зараз нам необхідно, по суті, написати власну рекурсію. Ідея полягає в наступному – спочатку ми проходимо “вниз” від N до початкових станів, запам’ятовуючи аргументи, функцію від яких нам треба буде обчислювати. Потім повертаємося “вгору”, послідовно обчислюючи значення від цих аргументів, в тому порядку, який ми записали.

Залежності обчислюються так:

LinkedList stack = new LinkedList();stack.add (n); {
LinkedList queue = new LinkedList();//Зберігаємо індекси, для яких ще не вичислені зависимостиqueue.add (n);int dum;while (queue.size ()>0){ //Поки є що обчислювати dum = queue.removeFirst (); if (dum%2==0){ //Перевіряємо парність if (dum/2>1){ //Якщо вичислена залежність не належить початковим станам stack.addLast (dum/2); //Додаємо в стек queue.add (dum/2); //Зберігаємо, щоб //вичислити подальші залежності } if (dum/2-1>1){ //Перевіряємо приналежність до початкових станів stack.addLast (dum/2-1); //Додаємо в стек queue.add (dum/2-1); //Сохрнаяем, щоб //вичислити подальші залежності } }else{ if ((dum - 1)/2>1){ //Перевіряємо приналежність до початкових станів stack.addLast ((dum - 1)/2); //Додаємо в стек queue.add ((dum - 1)/2); //Сохрнаяем, щоб
//вичислити подальші залежності } if ((dum - 1)/2-1>1){ //Перевіряємо приналежність до початкових станів stack.addLast ((dum - 1)/2-1); //Додаємо в стек queue.add ((dum - 1)/2-1); //Сохрнаяем, щоб //вичислити подальші залежності } }/*Конкретно для цього завдання є елегантніший спосіб знайти усі залежності, тут же показаний досить универсальный*/ }}

Отриманий розмір стека – те, скільки обчислень нам потрібно буде зробити. Саме так я отримав згадане вище число 172.

Тепер ми по черзі витягаємо індекси і обчислюємо для них значення за формулами – гарантується, що всі необхідні значення вже будуть обчислені. Зберігати будемо як раніше – в хеш-таблиці.

HashMap<Integer, Integer> values = new HashMap<Integer, Integer>();
values.put (0,1); // Важливо додати початкові стани//в таблицю значений values.put (1,1); while (stack.size ()>0){ int num = stack.removeLast (); if (!values.containsKey (num)){ //Цю конструкцію //ви повинні пам'ятати з абзаца про кешировании if (num%2==0){ //Перевіряємо парність int value = values.get (num/2) +values.get (num/2-1); //Обчислюємо значення values.add (num, value); //Поміщаємо його в таблицю }else{ int value = values.get ((num - 1)/2) - values.get ((num - 1)/2-1); //Обчислюємо значення values.add (num, value); //Поміщаємо його в таблицю } }

Усі необхідні значення обчислені, залишилося тільки написати

return values.get (n);

Звичайно, таке розв’язання набагато більше трудомістке, проте воно того варте.

Добре, математика – це красиво. А що із задачами, в яких не все дано?

Для більшої ясності розберемо наступну задачу на одновимірну динаміку:

На вершині сходів, яка має N сходинок, знаходиться м’ячик, який починає стрибати по них вниз, до підлоги. М’ячик може стрибнути на наступну сходинку, на сходинку через одну або через 2 (тобто, якщо м’ячик лежить на 8-й сходинці, то він може переміститися на 5-ту, 6-му або 7-му.) Визначте число всіляких “маршрутів” м’ячика з вершини на землю.

Ідея розв’язання

На першу сходинку можна потрапити тільки одним чином – зробивши стрибок довжиною, що дорівнює одиниці. На другу сходинку можна потрапити зробивши стрибок завдовжки 2, або з першої сходинки – всього 2 варіанти. На третю сходинку можна потрапити зробивши стрибок завдовжки три, з першої або з другої сходинок, тобто всього 4 варіанти (0 ->3; 0 ->1 ->3; 0 ->2 ->3; 0 ->1 ->2 ->3). Тепер розглянемо четверту сходинку. На неї можна потрапити з першої сходинки – по одному маршруту на кожен маршрут до неї, з другої або з третьої – аналогічно. Іншими словами, кількість шляхів до 4-ї сходинки є сума маршрутів до 1-ї, 2-ї і 3-ї сходинок. Математично виражаючись, F (N) = F (N - 1) +F (N - 2) +F (N - 3). Перші три сходинки вважатимемо початковими станами.

Реалізація через рекурсію

private static int f (int n){ if (n==1) return 1;
if (n==2) return 2; if (n==3) return 4; return f (n - 1) +f (n - 2) +f (n - 3);}

Тут нічого хитрого немає.

Реалізація через масив значень

Виходячи з того, що, за великим рахунком, просте розв’язання на масиві з N елементів очевидне, я продемонструю тут розв’язання на масиві всього з трьох.

int[] vars = new int[3];vars[0]=1;vars[1]=2;vars[2]=4; for (int i=3; i<N; i++){ vars[i%3] = vars[0]+vars[1]+vars[2]; }} System.out.println (vars[(N - 1)%3]);

Оскільки кожне наступне значення залежить тільки від трьох попередніх, жодне значення під індексом менше i - 3 нам би не згодилося. У наведеному вище коді ми записуємо нове значення на місце найстаршого, більше не потрібного. Циклічність залишку від ділення на 3 допомагає нам уникнути багатьох умовних операторів. Просто, компактно, елегантно.

Там вгорі ще було написано про якусь двовимірну динаміку?

З двовимірною динамікою не пов’язано жодних особливостей, проте я, про всяк випадок, розгляну тут одну задачу і на неї.

У прямокутній таблиці NxM спочатку гравець знаходиться в лівій верхній клітці. За один хід йому дозволяється переміщуватися в сусідню клітину або праворуч, або вниз (ліворуч і вгору переміщуватися заборонено). Розрахуйте, скільки є способів у гравця потрапити в праву нижню клітину.

Ідея розв’язання

Логіка розв’язання повністю ідентична тій, що в задачі про м’ячик і сходи – тільки тепер в клітину (x, y) можна потрапити з клітин (x - 1, y) чи (x, y - 1). Разом F (x, y) = F (x - 1, y) +F (x, y - 1). Додатково можна зрозуміти, що всі клітини виду (1, y) і (x, 1) мають тільки один маршрут – по прямій вниз або по прямій праворуч.

Реалізація через рекурсію

Не треба робити двовимірну динаміку через рекурсію. Вже було згадано, що рекурсія менш вигідна, ніж цикл до швидої кодії, так двовимірна рекурсія ще і читається жахливо. Це тільки на такому простому прикладі вона виглядає легко і нешкідливо.

private static int f (int i, int j) { if (i==1 || j==1) return 1; return f (i - 1, j) +f (i, j - 1);}

Реалізація через масив значень

int[][] dp = new int[Imax][Jmax]; for (int i=0; i<Imax; i++){ for (int j=0; j<Jmax; j++){ if (i==0 || j==0){ dp[i][j]=1; }else{ dp[i][j]=dp[i - 1][j]+dp[i][j - 1]; } }} System.out.println (dp[Imax - 1][Jmax - 1]);

Класичне розв’язання динамікою, нічого незвичайного – перевіряємо, чи є клітина краєм, і задаємо її значення на основі сусідніх клітин.

Відмінно, я все зрозумів. На чому мені перевірити свої навички?

На закінчення приведу ряд типових задач на одновимірну і двовимірну динаміку, розбір додається.

Вибухонебезпека

При переробці радіоактивних матеріалів утворюються відходи двох видів – особливо небезпечні (тип A) і безпечні (тип B). Для їх зберігання використовуються однакові контейнери. Після поміщення відходів у контейнери останні укладаються вертикальною стопкою. Стопка вважається вибухонебезпечною, якщо в ній підряд йде більше як один контейнер типу A. Стопка вважається безпечною, якщо вона не є вибухонебезпечною. Для заданої кількості контейнерів N визначте кількість можливих типів безпечних стопок.

Розв’язання

Відповіддю є (N+1)-е число Фібоначчі. Здогадатися можна було, просто обчисливши 2-3 перші значення. Строго довести можна було, побудувавши дерево можливих побудов.

Кожен основний елемент ділиться на два – основний (закінчується на B) і побічний (закінчується на A). Побічні елементи перетворюються на основні за одну ітерацію (до послідовності, що закінчується на A, можна дописати тільки B). Це характерно для чисел Фібоначчі.

Реалізація

Наприклад, так:

//Введення числа N з клавиатури N+=2;BigInteger[] fib = new BigInteger[2];fib[0]=fib[1]=BigInteger.ONE; for (int i=2; i<N; i++){ fib[i%2] = fib[0].add (fib[1]);} System.out.println (fib[(N - 1)%2]);

Підняття сходами

Хлопчик підійшов до платних сходів. Щоб наступити на будь-яку сходинку, треба заплатити вказану на ній суму. Хлопчик уміє переступати на наступну сходинку, або перестрибувати через сходинку. Потрібно дізнатися, яка найменша сума знадобиться хлопчикові, щоб дістатися до верхньої сходинки.

Розв’язання

Очевидно, що сума, яку хлопчик віддасть на N-й сходинці, є сума, яку він віддав до цього плюс вартість самої сходинки. “Сума, яку він віддав до цього” залежить від того, з якої сходинки хлопчик крокує на N-у – з (N – 1)-ї або з (N – 2)-ї. Вибирати треба найменшу.

Реалізація

Наприклад, так:

int Imax;//*введення з клавіатури числа сходинок*DP = new int[Imax]; for (int i=0; i<Imax; i++){ /// Введення з клавіатури вартості сходинки DP[i] } for (int i=2; i<DP.length; i++){ DP[i]+=Math.min (DP[i - 1], DP[i - 2]);} System.out.println (DP[Imax - 1]);

Калькулятор

Є калькулятор, який виконує три операції:

  • додати до числа X одиницю;
  • помножити число X на 2;
  • помножити число X на 3.

Визначте, яке найменше число операцій потрібне для того, щоб отримати з числа 1 задане число N. Виведіть це число, і, на наступному рядку, набір виконаних операцій виду ” 111231″.

Розв’язання

Наївне розв’язання полягає в тому, щоб ділити число на 3, поки це можливо, інакше на 2, якщо це можливо, інакше віднімати одиницю, і так до тих пір, поки воно не обернеться на одиницю. Це неправильне розв’язання, оскільки воно виключає, наприклад, можливість зменшити число на одиницю, а потім розділити на три, через що на великих числах (наприклад, 32718) виникають помилки.

Правильне розв’язання полягає в знаходженні для кожного числа від 2 до N мінімальної кількості дій на основі попередніх елементів, інакше кажучи: F (N) = min (F (N - 1), F (N/2), F (N/3)) + 1. Слід пам’ятати, що всі індекси мають бути цілими.

Для відтворення списку дій необхідно йти у зворотному напрямі і шукати такий індекс i, що F (i) =F (N), де N – номер даного елемента. Якщо i=N - 1, записуємо в початок рядка 1, якщо i=N/2 – двійку, інакше – трійку.

Реалізація
int N;//Введення з клавиатури int[] a = new int[N+1];a[1]= 0; {int min;for (int i=2; i<N+1; i++){ min=a[i - 1]+1; if (i%2==0) min=Math.min (min, a[i/2]+1); if (i%3==0) min=Math.min (min, a[i/3]+1); a[i] = min;}}StringBuilder ret = new StringBuilder (); { int i=N; while (i>1){ if (a[i]==a[i - 1]+1){ ret.insert (0, 1); i--; continue; } if (i%2==0&&a[i]==a[i/2]+1){ ret.insert (0, 2); i/=2; continue; } ret.insert (0, 3); i/=3; }}System.out.println (a[N]);System.out.println (ret);

Найдешевший шлях

У кожній клітині прямокутної таблиці N*M записано деяке число. Спочатку гравець знаходиться в лівій верхній клітці. За один хід йому дозволяється переміщуватися в сусідню клітину або праворуч, або вниз (ліворуч і вгору переміщуватися заборонено). При проході через клітину з гравця беруть стільки кілограмів їжі, яке число записане в цій клітині (їжу беруть також за першу і останню клітини його шляху).

Потрібно знайти мінімальну вагу їжі в кілограмах, віддавши яку гравець може потрапити в правий нижній кут.

Розв’язання

У будь-яку клітину таблиці ми можемо потрапити або з клітини, що знаходиться безпосередньо над нею, або з клітини, що знаходиться безпосередньо ліворуч. Таким чином, F (x, y) = min (F (x – 1, y), F (x, y – 1)). Щоб не обробляти граничні випадки, можна додати перший рядок і стовпець, заповнені деякою константою – якимсь числом, свідомо більшим вмісту будь-якої з клітин.

Реалізація
///nextInt () --- метод, що прочитує з консолі число int Imax=nextInt ();int Jmax=nextInt (); long[][] dp = new long[Imax][Jmax]; for (int i=0; i<Imax; i++){ for (int j=0; j<Jmax; j++){ dp[i][j]= nextInt (); if (i>0 && j>0){ dp[i][j]+=Math.min (dp[i - 1][j], dp[i][j - 1]); }else{ if (i>0){ dp[i][j]+=dp[i - 1][j]; }else if (j>0){ dp[i][j]+=dp[i][j - 1]; } } }} System.out.println (dp[Imax - 1][Jmax - 1]);

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *