Вход
Быстрая регистрация
Если вы у нас впервые: О проекте FAQ
2

Что такое динамическое программирование?

Esketit [7.4K] более года назад
1

Задачи на динамическое программирование - это такие алгоритмические задачи, в которых каждое новое состояние вы вычисляете через уже корректно посчитанные предыдущие состояния. Простейшими задачами на динамическое программирование являются: "Нахождение суммы на массиве", "Вывод первых N чисел Фибоначчи".

автор вопроса выбрал этот ответ лучшим
1

Суть динамического программирования состоит в том, что мы:

  • разбиваем сложную задачу на более простые — делать это можем как с использованием рекурсии (см. первый вариант решения), так и без нее;
  • используем мемоизацию результатов вычислений (накапливаем их и используем вместо повторного вычисления)

Отсюда следует, что динамическое программирование даст хороший результат только, когда:

  • задача является рекуррентной (более сложная выражается через более простые — возможно вручную рассчитать примеры как было показано выше с массивом step);
  • задачи пересекаются — как было показано выше, результат вычисления step[2] используется k раз.

Источник с примерами программ и т.п.

Знаете ответ?
Есть интересный вопрос? Задайте его нашему сообществу, у нас наверняка найдется ответ!
Делитесь опытом и знаниями, зарабатывайте награды и репутацию, заводите новых интересных друзей!
Задавайте интересные вопросы, давайте качественные ответы и зарабатывайте деньги. Подробнее..
регистрация