Код Middle Динамическое программирование обновлено
Нельзя брать соседние
Условие
Максимальная сумма элементов массива при условии, что нельзя брать два соседних.
Примеры
rob([1, 2, 3, 1]) // 4
rob([2, 7, 9, 3, 1]) // 12
rob([]) // 0
Как подойти
dp[i] = max(dp[i−1], dp[i−2] + nums[i]), свёрнутое до двух переменных. Умение свернуть массив динамики до констант - то, что отличает понимание от заучивания.
Подсказки: 2
- На каждом шаге выбор: взять текущий и пропустить соседа или пропустить текущий.
- Достаточно помнить два предыдущих результата.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Числа Фибоначчи с мемоизацией
Следующий вопрос
Наибольшая общая подпоследовательность