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];
}

interface TreeNode {
    value: number;
    children: TreeNode[];
}

function maxNonAdjacent(node: TreeNode | null): [number, number] {
    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];
}

def max_non_adjacent(node):
    if node is None:
        return (0, 0)  # (incl, excl)
    incl_sum = node.value
    excl_sum = 0
    for child in node.children:
        incl_c, excl_c = max_non_adjacent(child)
        incl_sum += excl_c
        excl_sum += max(incl_c, excl_c)
    return (incl_sum, excl_sum)

function maxNonAdjacent(?Node $node): array {
    if ($node === null) return [0, 0]; // [incl, excl]
    $inclSum = $node->value;
    $exclSum = 0;
    foreach ($node->children as $child) {
        [$inclC, $exclC] = maxNonAdjacent($child);
        $inclSum += $exclC;
        $exclSum += max($inclC, $exclC);
    }
    return [$inclSum, $exclSum];
}

    // returns {incl, excl}: the best sum that takes this node, and the best that skips it
    public static int[] maxNonAdjacent(TreeNode node) {
        if (node == null) return new int[] { 0, 0 };
        int inclSum = node.value;
        int exclSum = 0;
        for (TreeNode child : node.children) {
            int[] best = maxNonAdjacent(child);
            inclSum += best[1];
            exclSum += Math.max(best[0], best[1]);
        }
        return new int[] { inclSum, exclSum };
    }

    public static class TreeNode {
        public int value;
        public List<TreeNode> children = new ArrayList<>();
    }

    // returns {incl, excl}: the best sum that takes this node, and the best that skips it
    public static int[] MaxNonAdjacent(TreeNode node) {
        if (node == null) return new int[] { 0, 0 };
        int inclSum = node.value;
        int exclSum = 0;
        foreach (var child in node.children) {
            int[] best = MaxNonAdjacent(child);
            inclSum += best[1];
            exclSum += Math.Max(best[0], best[1]);
        }
        return new int[] { inclSum, exclSum };
    }

    public class TreeNode {
        public int value;
        public List<TreeNode> children = new List<TreeNode>();
    }

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 на деревьях» нужен, когда в условии есть слова «лучший выбор по иерархии или оргструктуре», «нельзя выбрать узел вместе с его прямым родителем» или «постпорядок: дети решаются раньше родителя». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «DP на деревьях» чаще всего путают с этими паттернами: Обход дерева, Динамическое программирование (1-D), Рекурсия с мемоизацией и Обход графа BFS / DFS.

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

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

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

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

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

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

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

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

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

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

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

Паттерн «DP на деревьях» решает такие задачи с собеседований: Ограбление домов III, Максимальная сумма пути в дереве, Диаметр двоичного дерева, Самый длинный путь из равных значений, Распределение монет в дереве, Число хороших узлов и Наклон дерева.

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

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

У паттерна «DP на деревьях» целевая сложность O(n).

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