Динамическое программирование: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Термин "кэширование" заменён на "мемоизация". |
|||
Строка 24:
''Перекрывающиеся подзадачи'' в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление [[числа Фибоначчи|последовательности Фибоначчи]], <math> F_3 = F_2 + F_1 </math> и <math> F_4 = F_3 + F_2 </math> — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали <math>F_2</math> дважды. Если продолжать дальше и посчитать <math>F_5</math>, то <math>F_2</math> посчитается ещё два раза, так как для вычисления <math>F_5</math> будут нужны опять <math>F_3</math> и <math>F_4</math>. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.
Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется
Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:
| |||