Динамическое программирование - это когда мы не знаем, как реш | Стадии принятия разработки

Динамическое программирование - это когда мы не знаем, как решать задачу, но сводим к таким же задачам поменьше, которые мы тоже не знаем как решать (тут надо посмеяться, если рассказываешь это на собеседовании, смех заразителен).

Исходя из определения, что нужно для дабл пенетрейшн ДП:
1. Состояние. Определиться с параметрами, которые будут определять нашу задачу (например для чисел фибоначчи это просто целое число - порядковый номер числа фибоначчи)
2. Переход. Вывести формулу, по которой мы будем из задач поменьше получать решение задачи побольше (f[n] = f[n-1] + f[n-2])
3. База. Где-то мы должны все-таки остановиться в наших рассуждений, или начать, если мы про код, так что нужны начальные условия (f[0] = 1, f[1] = 1)
4. Результат. Как из посчитанной динамики получать ответ для задачи (для чисел фибоначчи просто f[n])
5. Обход. В каком порядке для состояний считать результат задачи (для чисел фибоначчи считаем последовательно для 2, 3 и так до n)

Виды динамического программирования:
- линейное (у нас один параметр определяе задачу)
- двумерное (у нас 2 параметра)

Продвинутые:
- многомерное
- динамика по подотрезкам - состояние это границы отрезка
- динамика по поддеревьям
- динамика по помножествам
- динамика по профилю

Классические задачи:
- фибоначчи
- черепашка
- по ссылке

#пятиминутка #дп