DP на деревьях

DP на деревьях: как это работает?

Решите, что один узел возвращает родителю. Часто это пара, по значению на каждый вариант.

Сначала спуститесь во всех потомков. До их ответа ничего решить нельзя.

Соберите ответ узла из ответов потомков. Эта сборка и есть переход.

Верните результат наверх. Больше родитель о поддереве ничего не знает.

Если ответ может лежать где угодно, ведите глобальный максимум при возврате. Одного корня не всегда хватает.

Один обратный обход касается каждого узла один раз. В этом вся стоимость.

1. лист возвращает (3, 0)Грабим дома на дереве. Взять лист даёт 3, пропустить даёт 0.
2. узел 2 возвращает (2, 3)Взять его и пропустить потомка либо пропустить и взять лучшее.
3. узел 3 возвращает (3, 1)Его собственный потомок стоит всего 1.
4. корень взят = 3 + 3 + 1Взятие корня заставляет пропустить обоих потомков.
5. ответ = 7Семёрка бьёт шестёрку, которую даёт пропуск корня.

function maxNonAdjacent(node) {
    if (!node) return [0, 0]; // [incl, excl]
    let inclSum = node.value;
    let exclSum = 0;
    for (const child of node.children) {
        const [inclC, exclC] = maxNonAdjacent(child);
        inclSum += exclC;
        exclSum += Math.max(inclC, exclC);
    }
    return [inclSum, exclSum];
}

DP на деревьях: разбор примера

Наибольшая сумма по любому пути

Верните наибольшую сумму по любому пути в двоичном дереве.

Путь может начинаться и кончаться где угодно, но не может ветвиться дважды.

Каждый узел возвращает лучший прямой путь, идущий вниз через него.

Отрицательная ветка отбрасывается. Лучший разветвлённый путь пишется в глобальный максимум при возврате.

function maxPathSum(root) {
    let best = -Infinity;

    function down(node) {
        if (!node) return 0;

        // a negative branch is worse than taking nothing at all
        const left = Math.max(0, down(node.left));
        const right = Math.max(0, down(node.right));

        best = Math.max(best, node.val + left + right); // the fork stays local

        return node.val + Math.max(left, right); // the parent can only use one side
    }

    down(root);
    return best;
}

DP на деревьях: когда применять?

Эти формулировки в условии ведут сюда:

• •лучший выбор по иерархии или оргструктуре
• •нельзя выбрать узел вместе с его прямым родителем
• •постпорядок: дети решаются раньше родителя
• •каждый узел объединяет состояния своих детей

DP на деревьях: с чем путают?

• Обход дерева (Tree traversal): Та страница про порядок посещения. Эта про то, что уносится наверх.
• Динамическое программирование (1-D) (Dynamic programming (1-D)): У прямой одно направление, поэтому хватает индекса. Здесь порядок задаёт структура дерева.
• Рекурсия с мемоизацией (Recursion with memoization): В дереве подзадачи не повторяются, поэтому кеш не нужен. Каждый узел посещается один раз.
• Обход графа BFS / DFS (Graph BFS / DFS): В обычный граф можно попасть в узел дважды, и рекурсия может не кончиться. В дереве нельзя.

DP на деревьях: частые ошибки

• Возвращают то же, что и записывают

  Наверх уходит прямой путь, а лучший ответ может ветвиться. Держите их раздельно.

• Считают до ответа потомков

  Переходу сначала нужны оба потомка. Сначала спуск, потом сборка.

• Не разбирают случай пустого потомка

  Узел с одним потомком всё равно вызывает вторую сторону. Верните там нейтральное значение.

• Начинают максимум с нуля

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

DP на деревьях: задачи с собеседований

• Ограбление домов III: Два состояния на узел: взят или пропущен.
• Максимальная сумма пути в дереве: Возвращается прямой путь, записывается разветвлённый.
• Диаметр двоичного дерева: Глубина слева плюс глубина справа в каждом узле.
• Самый длинный путь из равных значений: Продолжать можно только через равных потомков.
• Распределение монет в дереве: Излишек передаётся наверх родителю.
• Число хороших узлов: Максимум несут вниз, а не наверх.
• Наклон дерева: Разность сумм двух поддеревьев.

DP на деревьях: сложность по времени и памяти

O(n)

n узлов дают O(n), если в узле работы на O(1). Несколько состояний на узел это умножают.