1 of 33

Очень динамическое программирование

Разделяй и властвуй, но помни!�Niccolò di Bernardo dei Machiavelli�Igor Mazurok

2 of 33

ПОПЫТКА ПЛАНА

Уравнение Беллмана
Интуитивное представление о динамике

Декомпозиция и рекурсия
Терминальный случай
Меморизация

Числа Фибоначчи и динамика вверх и вниз
Задача о двух единицах
Игра в умножение
Наидлиннейшая общая подстрока
Наидлиннейшая общая подпоследоватльность
Расстояние Левенштейна и проверка орфографии
Оптимальное перемножение матриц
Задачи для самостоятельного решения

3 of 33

Уравнение Беллмана

Ричард Эрнст Беллман (Richard Ernest Bellman; 1920—1984) — американский математик, один из ведущих специалистов в области математики и вычислительной техники.
Понятие Уравнения Беллмана и функции Беллмана применяется только для непрерывных систем. Для дискретных систем аналогом выступает так называемое основное рекуррентное соотношение, являющееся формальной основой метода динамического программирования и выражающее достаточное условие оптимальности, и функция будущих потерь.

4 of 33

Декомпозиция и рекурсия

Сводим задачу, которую мы не знаем как решать к одной или нескольким задачам меньшего размера, которые мы тоже не знаем как решать.
Принцип оптимальности подзадач – оптимальное решение исходной задачи строится из оптимальных решений подзадач.
Пример. Сортировка массива разбиением и слиянием (Merge Sort).

5 of 33

Терминальный случай

Снижение размера задачи должно приводить к очевидному случаю с простым или тривиальным решением
Например, массив размера 1 (или лучше 0?) уже отсортирован. И по возрастанию, и по убыванию!

6 of 33

Мемо р и зация

Количество подзадач растет.
Количество подзадач иногда сильно растет
Количество подзадач иногда очень сильно растет
Количество подзадач иногда экспоненциально, например задачи раздваиваются

А как растет количество разных подзадач?
Часто оно растет «не сильно»

Выход: Нужно запоминать ответы!

7 of 33

Подходы к решению

Метод динамического программирования сверху вниз — запоминание результатов решения подзадач, которые могут повторно встретиться в дальнейшем. Очередность решения подзадач контролирует рекурсия

Динамическое программирование снизу вверх включает в себя переформулирование сложной задачи в виде последовательности подзадач, каждая из которіх строится на уже найденных решениях.

8 of 33

Числа Фибоначчи

Посмотрим на последовательность имени Леонардо пизанского по кличке Фибоначчи
0 1 1 2 3 5 8 13 21 24 45 69…

http://cpp.mazurok.com/fib

9 of 33

Динамика сверху вниз

http://cpp.mazurok.com/fib

#include <iostream>

#define MAX 100

using namespace std;

long long fib[MAX];

long long f(int n) {

if (n < 2) return n;

else if (fib[n] != 0) return fib[n];

else return fib[n] = f(n-1) + f(n-2);

}

int main() {

cout << f(87) << endl;

return 0;

}

10 of 33

Динамика снизу вверх

#include <iostream>

using namespace std;

long long f(int n) {

if (n < 2) return n;

else {

long long yesterday = 0, today = 1;

while(--n > 0) {

long long tomorrow = yesterday + today;

yesterday = today;

today = tomorrow;

}

return today;

}

int main() {

cout << f(87);

return 0;

}

11 of 33

Динамика снизу вверх

0 → Yesterday

1 → Today

? → Tomorrow

12 of 33

Динамика снизу вверх

0 → Yesterday

1 → Today

1 → Tomorrow

13 of 33

Динамика снизу вверх

0

1 → Yesterday

1 → Today

? → Tomorrow

14 of 33

Динамика снизу вверх

0 Yesterday

1 → Yesterday Today

1 → Today Tomorrow

? → Tomorrow

15 of 33

Динамика снизу вверх

0 Yesterday

1 → Yesterday Today

1 → Today Tomorrow

2 → Tomorrow

16 of 33

Динамика снизу вверх

0 Yesterday

1 Yesterday Today

1 → Yesterday Today Tomorrow

2 → Today Tomorrow

? → Tomorrow

17 of 33

Динамика снизу вверх

0 Yesterday

1 Yesterday Today

1 → Yesterday Today Tomorrow

2 → Today Tomorrow

3 → Tomorrow

18 of 33

Динамика снизу вверх

0 Yesterday

1 Yesterday Today

1 Yesterday Today Tomorrow

2 → Yesterday Today Tomorrow

3 → Today Tomorrow

? → Tomorrow

19 of 33

Динамика снизу вверх

0 Yesterday

1 Yesterday Today

1 Yesterday Today Tomorrow

2 → Yesterday Today Tomorrow

3 → Today Tomorrow

5 → Tomorrow

20 of 33

Динамика снизу вверх

0 Yesterday

1 Yesterday Today

1 Yesterday Today Tomorrow

2 Yesterday Today Tomorrow

3 → Yesterday Today Tomorrow

5 → Today Tomorrow

? → Tomorrow

21 of 33

Динамика снизу вверх

0 Yesterday

1 Yesterday Today

1 Yesterday Today Tomorrow

2 Yesterday Today Tomorrow

3 → Yesterday Today Tomorrow

5 → Today Tomorrow

8 → Tomorrow

…

22 of 33

Задача о двух единицах

Сколько существует битовых последовательностей длины N в которых не встречаются две единицы подряд?

Рассматриваем “короткие” случаи:

Для N = 0 существует единственная пустая последовательность, значит� f(0) = 1
Для N = 1 существуют две последовательности — 0 и 1. Обе подходят.� f(1) = 2
Для N = 2 существуют 4 последовательности — 00 01 10 11. Но одна не подходит, значит� f(2) = 3

23 of 33

Задача о двух единицах

Ищем способ свести задачу вычисления f(N) к более “коротким”, т.е. к вычислению f(n<N).

Первый подход

Пусть у нас есть подходящая последовательность длины N-1.

Если она заканчивается на 0, то есть два варианта — к ней можно дописать либо 0, либо 1. А как получилась такая последовательность длины N-1 с ноликом в конце? Просто взяли любую подходящую последовательность длины N-2 и дописали 0. Это не приведет к получению двух 1 подряд. Сколько таких последовательностей длины N-2? f(N-2). Дописывая к каждой либо 0, либо 1, получим 2f(N-2) вариантов.
Если она заканчивается на 1, а 11 запретная комбинация, то значит в конце стоит 01. Остальные N-3 символа — любая легальная комбинация. Получаем f(N-2) варианта

Всего получаем f(N) = 2*f(N-2) + f(N-3)

24 of 33

Задача о двух единицах

Ищем способ свести задачу вычисления f(N) к более “коротким”, т.е. к вычислению f(n<N).

Второй подход

Пусть у нас есть подходящая последовательность длины N.

Если она заканчивается на 0, то слева от нее может быть любая правильная последовательность длины N-1. Значит таких последовательностей всего будет f(N-1).
Если она заканчивается на 1, а 11 запретная комбинация, то значит в конце стоит 01. Остальные N-2 символа — любая легальная комбинация. Получаем f(N-2) варианта

Итого f(N) = f(N-1) + f(N-2)

25 of 33

Задача о двух единицах

Какой ответ правильный?

f(N) = 2*f(N-2) + f(N-3)

f(N) = f(N-1) + f(N-2)

https://ideone.com/Irb5bX

Как из второй формулы получить первую?�А из первой вторую?

26 of 33

Задача о двух единицах

А три единицы?

27 of 33

#656 Игра умножения

Слава и Оля играют в игру умножения – умножают целое число P на одно из чисел от 2 до 9. Слава всегда начинает с P=1, делает умножение, затем число умножает Оля, затем Слава и т.д. Перед началом игры им задают число N, и победителем считается тот, кто первым получит P ≥ N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.

long long n;�map <long long, bool> x;�

bool isWin(long long value) {� auto it = x.find(value);� if (it != x.end()) return it->second;� bool isCurWin = false;� for (int i = 2; i <= 9; i++) {� if(i*value >= n || !isWin(i*value)){� isCurWin = true;� break;� } }� x[value] = isCurWin;� return isCurWin;�}�int main() {� cin >> n;� if (isWin(1)) cout << "Stan wins.";� else cout << "Ollie wins.";� return 0;�}

Измените заголовок цикла так, чтобы не использовать “break”

28 of 33

Наидлиннейшая общая подстрока

The Longest common substring problem
Ищем самый длинный суффикс подстрок

29 of 33

Наибольшая общая подпоследоватльность

The longest common subsequence (LCS) problem

Наибольшая алфавитная подпоследовательность
Задача о слонах - больше, значит умнее!

30 of 33

Расстояние Левенштейна и проверка орфографии

Редакционным предписанием называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом.
Обычно действия обозначаются так: D (delete) — удалить, I (insert) — вставить, R (replace) — заменить, M (match) — совпадение.

31 of 33

Оптимальное перемножение матриц

32 of 33

Задачи для самостоятельного решения

Задачи для самостоятельного решения и тестирования�http://cpp.mazurok.com/in-class-assignment/dynamic-programming/
Решения некоторых из них�http://cpp.mazurok.com/category/dynamic-programming/

Стоит посмотреть видео

33 of 33

Задачи для самостоятельного решения

Вспомним жадность - � #796. Стабильное бракосочетание�Динамика -
#4054. Три единицы подряд
#656. Игра умножения
#15. Мышка и зернышки
#5062. Максимальный подпалиндром
#1285. Деление Гольдбаха
#7447. Обрезка строки
#1521. Оптимальное умножение матриц
#595. Новый Лабиринт Амбера