Динамическое программирование было введено Ричардом Беллманом в 1953 году. Термин «динамическое программирование» не имеет ничего общего с тем, что оно на самом деле делает. В этом нет ничего динамичного. Как оказалось, Беллман проводил какое-то исследование, и он хотел скрыть это от своего босса, поскольку его босс ненавидел все, что имело отношение к исследованиям. Поэтому он придумал термин, чтобы это звучало круто, что-то, что получило бы одобрение от его босса, чтобы позволить ему продолжить свои исследования. Теперь, если вас спросят о динамическом программировании на собеседовании, не говорите BS; Возможно, ты не так умен, как Беллман, чтобы справиться с этим. Все, что вам нужно знать о динамическом программировании, можно прочитать менее чем за 5 минут.
В любом случае, что это за динамическое программирование?
Динамическое программирование - это метод решения сложной проблемы путем:
- Разбиение сложной проблемы на более мелкие, легко решаемые подзадачи
- Однократное решение подзадач и сохранение результата в структуре данных, предпочтительно в хэш-таблице.
- Использование значения из структуры данных вместо повторного решения той же подзадачи всякий раз, когда возникает необходимость
Другими словами, «Динамическое программирование» = (рекурсия + мемоизация)
Например: при использовании рекурсии для вычисления n-го числа Фибоначчи функция разбивает задачу на гораздо более мелкие подзадачи, а затем решает их одну за другой. Но это не самый оптимальный способ найти n-е число Фибоначчи. Давайте посмотрим, что на самом деле делает код. Я нарисовал картину всех подзадач, которые созданы для решения 4-го числа Фибоначчи. Вы можете видеть, что когда мы применяем рекурсию только к этой проблеме, нам приходится выполнять некоторую избыточную работу. Например, мы вычисляем Fib (1) трижды и аналогично Fib (2) дважды. Это не такая уж большая проблема при работе с небольшими числами, но Python Tutor превысит предел в 1000 шагов при попытке вычислить 11-е число Фибоначчи.
Теперь давайте посмотрим, как решить ту же проблему, добавив мемоизацию, то есть, в приведенном выше случае, вычислив fib (1) только один раз и сохранив его в объекте Dictionary. На картинке ниже я прикрепил два набора кода для вычисления n-го числа Фибоначчи. Тот, что слева, использует динамическое программирование, а тот, что справа, использует только рекурсию. Самая важная вещь, на которую следует обратить внимание, - это при использовании исключительно рекурсии (код справа на рисунке ниже) Python Tutor превысит ограничение в 1000 шагов при вычислении 11-го числа Фибоначчи (вызов функции в строке 6). Однако при использовании динамического программирования (код слева) даже вычисление 99-го числа Фибоначчи (вызов функции в строке 10) займет всего 990 шагов.
У динамического программирования есть множество реальных приложений, с одним из которых вы можете столкнуться в повседневной поездке на работу. Итак, в следующий раз, когда вы воспользуетесь Apple или Google Maps для поиска наиболее оптимального маршрута по дороге на работу, приложение карты могло быть разработано с использованием динамического программирования.
