На этом шаге мы рассмотрим понятия динамическое программирование
"сверху вниз" и "снизу вверх".
Возможно два варианта вычисления оптимального значения параметра для всей задачи (этап 3 алгоритма решения задач методом динамического программирования):
- Если задачу решаем рекурсивно, значит, процедура делит заданную ей задачу на
подзадачи (предварительно выяснив, не является ли задача тривиальной, и, проверив, не решалась ли она
ранее - тогда нужно лишь взять уже готовое решение из соответствующего массива) и, получив
решение, ставит флаг, что эта подзадача уже решена. Такое решение называется
решением "сверху вниз" - то есть берем глобальную задачу, потом решаем только
необходимые для нее подзадачи.
- Если же рекурсия невозможна по техническим или еще каким-нибудь причинам, то применяется такой подход: решаются сначала элементарные подзадачи, потом только те, которые требуют результатов уже решенных подзадач и так далее, пока не будет решена общая задача. Такой метод называется решением "снизу вверх" - в большинстве случаев он оказывается быстрее, но менее понятным и простым.
Вообще говоря, если каждая из подзадач должна быть решена хоть раз, метод динамического программирования ("снизу вверх") обычно эффективнее, чем рекурсия с запоминанием ответов, поскольку реализация рекурсии (а также проверка, есть ответ в таблице или еще нет) требует дополнительного времени. Но если для нахождения оптимума не обязательно решать все подзадачи, подход "сверху вниз" имеет то преимущество, что решаются лишь те подзадачи, которые действительно нужны.
Таким образом, рассмотрены два варианта вычисления оптимального параметра для
всей задачи.
На следующем шаге мы приведем несколько примеров решения задач методом динамического программирования.
