В информатике говорят, что проблема имеет перекрывающиеся подзадачи, если проблема может быть разбита на подзадачи, которые повторно используются несколько раз, или рекурсивный алгоритм для проблемы решает одну и ту же подзадачу снова и снова, а не всегда генерирует новые подзадачи.
Что такое оптимальная подструктура и перекрывающиеся подзадачи в динамическом программировании?
Задача обладает свойством оптимальной подструктуры, если оптимальное решение данной задачи может быть получено с использованием оптимального решения ее подзадач. Динамическое программирование использует это свойство для поиска решения.
Что такое перекрывающаяся подзадача в динамическом программировании?
1) Перекрывающиеся подзадачи:
Динамическое программирование в основном используется, когда необходимо снова и снова решать одни и те же подзадачи. В динамическом программировании вычисленные решения подзадач хранятся в таблице, поэтому их не нужно вычислять заново.
В чем разница между оптимальной подструктурой и перекрывающимися подзадачами?
Я понимаю целевой подход для обоих методов, где Оптимальная подструктура вычисляет оптимальное решение на основе входных данных n, а Перекрывающиеся подзадачи нацелены на все решения для диапазона входных данных, скажем, от 1 до n. Для такой задачи, как задача о перерезании стержня.
Какая из этих техник использует перекрытие подзадач?
Динамическое программирование - это метод решения задач с перекрывающимися подзадачами. При этом мы сохраняем результат подзадачи, решенной один раз, для повторного использования в будущем. Техника запоминания решений подзадач называется мемоизацией.
