Максимальная непрерывная сумма в двоичном дереве за N переходов

Дано двоичное дерево, со значениями весов перехода. Нужно получить максимальное значение за N переходов начиная с нулевого узла. При этом путь должен быть непрерывный,с бесплатными возвратами в родительский узел.
Мой текущий алгоритм:
Найти последний доступный узел(в котором количество ходов равно 0, либо отсутствуют дети). Записать в массив текущее значение и количество доступных ходов(с учетом потомков). Перейти в родительский узел, скопировать оба массива(если 2 потомка), либо 1 массив (1 потомок). Повторять п.2-3 до возврата в корневой узел. На основании массива в корневом узле (в котором находятся все возможные сочетания значений+ходов) найти максимальное значение.
Основные вопросы:
Существует ли лучший алгоритм? Возможно ли оптимизировать данный алгоритм т.к. работает слишком долго и требует слишком много памяти?

Ответ

Решение за N*S памяти, N*S*S или N*S*log S времени. S - размер дерева
Динамика F[vert][size] - оптимальный ответ если мы в поддереве вершины vert берём size элементов.
Для любого элемента F[u][0] = 0 Для листа на этом всё.
Для вершины псевдокод. (r - правый потомок, l - левый).
for (int i=0;iКак-то так. Мы либо берём только с 1 поддерева элементы. Либо берём с 2, тогда перебираем сколько берём слева и сколько справа.
Ответ - значение в F[root][N]. Для ускорения вместо двойного цикла использовать Быстрое преобразование Фурье (FFT)