Take/skip, число способов, min/max

Одномерный DP часто выглядит как таблица по индексам, но операции в переходе меняют смысл: сумма считает варианты, min ищет цену, max выбирает выгоду. Здесь рассмотрим типичный выбор take/skip: максимальную сумму неприходящих рядом элементов.

Как выбрать несоседние значения с максимумом

Дан массив неотрицательных чисел — ценности домов на улице. Нельзя брать два соседних дома. Для [2, 7, 9, 3, 1] оптимально взять 2 + 9 + 1 = 12.

Что перебирает каждое подмножество позиций

Для каждого индекса есть две ветви: взять элемент и перескочить через соседа или пропустить его. Это O(2^n) вариантов. Одна и та же задача для префикса повторяется после разных ранних решений.

Почему выбор текущего элемента повторяет прошлое

История того, какие дома взяты раньше, не важна целиком. Важно только лучшее допустимое значение на префиксе, который уже не конфликтует с текущим индексом.

Какие две прошлые прибыли достаточно сравнить

Пусть dp[i] — максимум на первых i элементах (индексы от 0 до i-1). Для очередного value = values[i-1] есть два честных варианта: не брать его и оставить dp[i-1], либо взять и добавить к dp[i-2]. Поэтому dp[i] = max(dp[i-1], dp[i-2] + value).

Что означает лучший ответ на префиксе

После вычисления dp[i] в нём лежит точный максимум для первых i домов без соседних выбранных индексов. В частности, dp[i] >= dp[i-1]: можно всегда повторить прошлое решение и ничего не брать.

Как пройти массив без соседнего конфликта

1. Задать dp[0] = 0: на пустом префиксе выгода 0.
2. Задать dp[1] = values[0] при непустом массиве.
3. Для каждого следующего префикса сравнить skip = dp[i-1] и take = dp[i-2] + values[i-1].
4. Записать больший вариант.

Как оставить только две нужные величины

Функция хранит всю таблицу для учебной трассировки. После понимания перехода её можно заменить двумя переменными previousTwo и previousOne.

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

int maxNonAdjacentSum(const vector<int>& values) {
    vector<int> dp(values.size() + 1, 0);
    if (values.empty()) return 0;

    dp[1] = values[0];
    for (size_t length = 2; length <= values.size(); ++length) {
        int skip = dp[length - 1];
        int take = dp[length - 2] + values[length - 1];
        dp[length] = max(skip, take);
    }
    return dp.back();
}

int main() {
    assert(maxNonAdjacentSum({2, 7, 9, 3, 1}) == 12);
    assert(maxNonAdjacentSum({2, 1, 1, 2}) == 4);
    cout << maxNonAdjacentSum({5, 1, 1, 5}) << '\n';
}

Python 3

def max_non_adjacent_sum(values: list[int]) -> int:
    dp = [0] * (len(values) + 1)
    if not values:
        return 0

    dp[1] = values[0]
    for length in range(2, len(values) + 1):
        skip = dp[length - 1]
        take = dp[length - 2] + values[length - 1]
        dp[length] = max(skip, take)
    return dp[-1]


assert max_non_adjacent_sum([2, 7, 9, 3, 1]) == 12
assert max_non_adjacent_sum([2, 1, 1, 2]) == 4
print(max_non_adjacent_sum([5, 1, 1, 5]))

Почему память можно сделать постоянной

Время O(n), память O(n) с таблицей или O(1) после сжатия. В этом уроке значения неотрицательные, поэтому база dp[1] = values[0] безопасна. Если разрешены отрицательные и можно не брать ничего, нужно использовать max(0, values[0]).

Как пустой префикс влияет на максимум

Пустой массив даёт 0, один элемент — его ценность. Два элемента требуют выбрать максимум, а не их сумму. Равные ценности дают несколько одинаково хороших наборов, но значение ответа одно. Ошибка «взять текущий плюс dp[i-1]» незаконно берёт соседей.

На каких наборах видно неверный переход

• [] -> 0, [8] -> 8, [4,9] -> 9;
• [2,7,9,3,1] -> 12;
• [2,1,1,2] -> 4, где ответ берёт края;
• одинаковые значения [5,5,5,5] -> 10;
• сравнить с перебором всех масок для коротких массивов.

Когда выбор исключает соседа

Сигналы: «взять или пропустить», «нельзя брать соседние», «лучший результат на префиксе», «последний выбор блокирует ближайшее будущее». Прежде чем писать формулу, назовите обе ветви и проверяйте, что в take остаётся совместимый префикс.

Когда нужна информация о нескольких прошлых элементах

Если можно брать соседей с небольшим штрафом, состояние меняется. Если нужно восстановить сами индексы, одной таблицы значений недостаточно: добавьте обратный проход или решение для каждого i. Для задач «посчитать число способов» вместо max будет сложение, и база также изменится.

Самопроверка выбора или пропуска

Вопрос: почему take использует dp[i-2], а не dp[i-1]?
Ответ: в dp[i-1] может быть выбран соседний элемент, который конфликтует с текущим. Префикс длины i-2 гарантированно отстоит на один индекс.

Самопроверка сжатого состояния

Вопрос: чему равно dp[3] для [2,7,9]?
Ответ: max(dp[2]=7, dp[1]+9=11) = 11; выбираются значения 2 и 9.

Потренируйте максимум без соседей

Решите «нельзя брать дома на расстоянии не более двух». Сначала замените в формуле допустимый предыдущий префикс, затем вручную заполните таблицу для [3,2,7,10,12]. Подсказка: при взятии индекса i-1 нужен префикс, заканчивающийся до двух запрещённых соседей.

Самостоятельный выбор без соседних позиций

Сделайте независимую попытку и объясните, что меняется, если значения могут быть отрицательными.

Задача 1

Дан ряд ячеек с прибылью. Нельзя выбирать две ячейки на расстоянии меньше трёх. Найдите максимальную сумму и определите минимальное состояние для решения.

Что остаётся после сжатия DP

В переходе take/skip смысл каждой ветви важнее имени dp. Состояние должно исключать конфликт, а агрегатор (max, min или сумма) должен соответствовать вопросу задачи.