Выбор ответа Middle Динамическое программирование обновлено
Грабитель домов
Вопрос
Нельзя грабить два соседних дома. Какой переход верен для максимальной суммы dp[i] по первым i домам?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: dp[i] = max(dp[i-1], dp[i-2] + a[i]). Для дома i два варианта: пропустить его (dp[i-1]) или ограбить и тогда предыдущий нельзя (dp[i-2] + a[i]).
Варианты ответа
dp[i] = dp[i-1] + a[i], еслиa[i] > 0dp[i] = max(a[i], a[i-1])по двум домамdp[i] = dp[i-2] + a[i]при любом idp[i] = max(dp[i-1], dp[i-2] + a[i])правильный ответ
Разбор
Для дома i два варианта: пропустить его (dp[i-1]) или ограбить и тогда предыдущий нельзя (dp[i-2] + a[i]). Берём лучший.
dp[i-1] + a[i]разрешает грабить соседей.- Максимум двух домов не учитывает остальные.
- Всегда грабить i неверно: иногда выгоднее пропустить.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.