Алгоритми та структури даних · Middle · Запитання 40 з 75
Які дві властивості роблять задачу придатною для динамічного програмування?
- 1Відсортовані дані й одна унікальна відповідь
- ✓Правильна відповідь: Підзадачі, що перекриваються, і оптимальна підструктура
- 3Структура графа з додатними вагами ребер
Пояснення
Підзадачі перекриваються, коли ті самі проміжні результати потрібні багато разів, тож кешувати їх вигідно. Оптимальна підструктура означає, що найкраща відповідь складається з найкращих відповідей на підзадачі.