Выбор ответа Junior Динамическое программирование спрашивают часто обновлено
Признак динамики
Вопрос
Какое сочетание в условии сильнее всего указывает на динамическое программирование?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: «Сколько способов» или «минимум» плюс повторяющиеся подзадачи в рекурсии. DP нужна, когда ответ складывается из ответов на меньшие подзадачи, и эти подзадачи повторяются.
Варианты ответа
- «Отсортированный массив» и «найти элемент с заданным значением»
- «Кратчайший путь в графе без весов» от одной вершины до другой
- «Сколько способов» или «минимум» плюс повторяющиеся подзадачи в рекурсииправильный ответ
- «Найти пару с суммой» в массиве и вернуть индексы этой пары
Разбор
DP нужна, когда ответ складывается из ответов на меньшие подзадачи, и эти подзадачи повторяются. Типичные формулировки: «сколько способов», «минимальная стоимость», «самая длинная подпоследовательность».
- Отсортированный массив и поиск это бинпоиск.
- Кратчайший путь без весов это BFS.
- Пара с суммой это хеш или два указателя.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.