Перекрывающиеся подзадачи
-
Определение и примеры
- Задача имеет перекрывающиеся подзадачи, если она может быть решена с использованием одних и тех же подзадач несколько раз.
- Задача вычисления последовательности Фибоначчи является примером с перекрывающимися подзадачами.
-
Сложность и оптимизация
- Нативный рекурсивный подход к задаче Фибоначчи имеет экспоненциальную сложность.
- Динамическое программирование может быть эффективным методом решения задач с перекрывающимися подзадачами и оптимальной подструктурой.
-
Пример кода на Си
- В статье представлен пример кода на Си для вычисления последовательности Фибоначчи.
- Функция fibMem оптимизирована для использования уже вычисленных значений, что уменьшает сложность.
-
Визуализация эффективности
- Диаграммы показывают разницу в сложности между исходной функцией Фибоначчи и оптимизированной версией.
-
Дополнительные ресурсы
- Ссылки на книги и видеоматериалы по динамическому программированию.