Выбор ответа Middle Динамическое программирование обновлено
Инициализация в размене монет
Вопрос
Минимум монет для суммы: dp[0] = 0, остальные заполняют Infinity. Почему не нулями?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: При нулях min всегда даст 0, недостижимое станет бесплатным. dp[s] = min(dp[s], dp[s - c] + 1).
Варианты ответа
- Нули тоже работают: недостижимые суммы останутся нулями и отсеются
Infinityбыстрее: сравнение с ним движок оптимизирует- При нулях
minвсегда даст 0, недостижимое станет бесплатнымправильный ответ - Нули дадут ошибку типов при сложении
dp[s - c] + 1
Разбор
dp[s] = min(dp[s], dp[s - c] + 1). Если стартовые значения 0, минимум сразу 0, и ответ всегда 0. Infinity значит «пока недостижимо», и в конце Infinity превращается в -1.
- Нули ломают минимум.
- Скорость не меняется.
- Ошибки типов нет: это молча неверный ответ.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.