Карточка Middle Жадные обновлено
Жадность или динамика
Вопрос
Как понять, хватит ли жадности или нужна динамика?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Ищи контрпример на маленьких входах: если локально лучший шаг может испортить будущее (монеты 1, 3, 4 на сумме 6), нужна динамика. Если можно доказать обменным аргументом, что жадный шаг совместим с оптимумом, хватит жадности.
Ответ
Ищи контрпример на маленьких входах: если локально лучший шаг может испортить будущее (монеты 1, 3, 4 на сумме 6), нужна динамика. Если можно доказать обменным аргументом, что жадный шаг совместим с оптимумом, хватит жадности.
Разбор
Ищи контрпример на маленьких входах: если локально лучший шаг может испортить будущее (монеты 1, 3, 4 на сумме 6), нужна динамика. Если можно доказать обменным аргументом, что жадный шаг совместим с оптимумом, хватит жадности.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.