В информатике говорят , что проблема имеет перекрывающиеся подзадачи , если проблема может быть разбита на подзадачи, которые повторно используются несколько раз, или рекурсивный алгоритм проблемы решает одну и ту же подзадачу снова и снова, а не всегда генерирует новые подзадачи. [1] [2] [3]
Например, проблема вычисления последовательности Фибоначчи демонстрирует перекрывающиеся подзадачи. Задача вычисления n -го числа Фибоначчи F ( n ) может быть разбита на подзадачи вычисления F ( n -1) и F ( n -2) и последующего сложения двух. Сама подзадача вычисления F ( n - 1) может быть разбита на подзадачу, которая включает вычисление F ( n - 2). Следовательно, вычисление F ( n − 2) используется повторно, и, таким образом, последовательность Фибоначчи демонстрирует перекрывающиеся подзадачи.
Наивный рекурсивный подход к такой проблеме обычно терпит неудачу из-за экспоненциальной сложности . Если проблема также имеет свойство оптимальной подструктуры , динамическое программирование — хороший способ решить ее.
При выполнении fibonacciфункция многократно вычисляет значение некоторых чисел в последовательности, следуя шаблону, который можно представить на этой диаграмме:
Однако мы можем воспользоваться преимуществами запоминания и изменить fibonacciфункцию так, чтобы она использовалась fibMemследующим образом:
Это намного эффективнее, потому что, если значение rуже было рассчитано для определенного nи сохранено в fibMem[n - 1], функция может просто вернуть сохраненное значение, а не выполнять дополнительные рекурсивные вызовы функций. В результате получается шаблон, который можно визуализировать на этой диаграмме: