Где применяется
1. Задача
Ты собираешь небольшую рабочую группу по схеме компании (оргчарту). У каждого человека есть балл «влияния», и нужно набрать наибольшую сумму баллов. Правило одно: нельзя брать в группу руководителя вместе с его прямым подчинённым, они будут мешать друг другу.
Значит, нужен набор людей с наибольшей суммой баллов, в котором нет пары «начальник и его прямой подчинённый».
Простые догадки не работают. Если взять всех с высоким баллом, среди них окажутся руководитель и его подчинённый. Если брать людей через уровень, можно без причины потерять ценного человека. Нужен способ, который для каждого человека сравнивает выгоду от него с тем, что из-за него придётся отдать ниже по дереву.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmaxNonAdjacent(root) // root = [3, 4, 5, 1, 3, null, 1]Выбираем узлы с самой большой суммой так, чтобы среди выбранных не было родителя и потомка. Каждый узел сообщит два числа: лучшее, если его взять, и лучшее, если пропустить.
Как узнать
Эти слова в условии значат этот паттерн
- лучший выбор по иерархии или оргструктуре
- нельзя выбрать узел вместе с его прямым родителем
- постпорядок: дети решаются раньше родителя
- каждый узел объединяет состояния своих детей
Похоже, но не то
- Обход дерева (Tree traversal)
Та страница про порядок посещения. Эта про то, что уносится наверх.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
У прямой одно направление, поэтому хватает индекса. Здесь порядок задаёт структура дерева.
- Рекурсия с мемоизацией (Recursion with memoization)
В дереве подзадачи не повторяются, поэтому кеш не нужен. Каждый узел посещается один раз.
- Обход графа BFS / DFS (Graph BFS / DFS)
В обычный граф можно попасть в узел дважды, и рекурсия может не кончиться. В дереве нельзя.
n узлов дают O(n), если в узле работы на O(1). Несколько состояний на узел это умножают.
На LeetCode
Задачи на деревья, где каждый узел возвращает родителю два или три числа, например лучшую сумму, если узел взят, и если нет. Один обход post-order считает их от листьев вверх.
Задача урока на двоичном дереве. Для каждого узла верни сумму, если он взят, и сумму, если пропущен.
Каждое поддерево возвращает свои монеты минус свои узлы, и число ходов по ребру над ним равно модулю этого числа.
Каждый узел возвращает лучший путь вниз от себя, а ответ в этом узле соединяет два его лучших пути вниз.
Каждый узел возвращает одно из трёх состояний, стоит камера, покрыт или нужна камера, и родитель решает по состояниям детей.