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

#алгоритм #дерево #теория

Дано двоичное дерево, со значениями весов перехода.
Нужно получить максимальное значение за N переходов начиная с нулевого узла. При
этом путь должен быть непрерывный,с бесплатными возвратами в родительский узел.

Мой текущий алгоритм:


Найти последний доступный узел(в котором количество ходов равно 0, либо отсутствуют
дети).  
Записать в массив текущее значение и количество доступных ходов(с учетом потомков).
Перейти в родительский узел, скопировать оба массива(если 2 потомка), либо 1 массив
(1 потомок).
Повторять п.2-3 до возврата в корневой узел.
На основании массива в корневом узле (в котором находятся все
возможные сочетания значений+ходов) найти максимальное значение.


Основные вопросы:


Существует ли лучший алгоритм?
Возможно ли оптимизировать данный алгоритм т.к. работает слишком
долго и требует слишком много памяти?

    

Ответы

Ответ 1

Решение за 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
Ответ 2

Собственно ответ,возможно пригодится кому-то:
В дереве всегда добавляю сначала левую ноду , затем правую(см. if(left!=NULL & right==NULL).

void getMax(Node *curr,int turns)
{
    int i,j;
    if(curr->left!=NULL && turns!=0)
        getMax(curr->left,turns-1);
    if(curr->right!=NULL && turns!=0)
        getMax(curr->right,turns-1);
    curr->res=new int[turns+1]();
    curr->res[0]=0;
    if(curr->left==NULL && curr->right==NULL || turns==0)
    {
        for(i=1;ires[i]=0;
        return;
    }
    else
    {
        if(curr->left!=NULL && curr->right==NULL)
        {
            Node*next=curr->left;
            for(i=0;ires[i+1]=next->res[i]+next->value;
            }
        }
        else
        {
                Node *left=curr->left;
                Node *right=curr->right;
                for(i=0;ires[0]=0;
                            }
                            if(i==0 && j>=1)
                            {
                                curr->res[j]=max(curr->res[j],right->value+right->res[j-1]);
                            }
                            if(i>=1 && j==0)
                            {
                                curr->res[i]=max(curr->res[i],left->value+left->res[i-1]);
                            }
                            if(i>=1 && j>=1)
                            {
                                curr->res[i+j]=max(curr->res[i+j],left->value+right->value+left->res[i-1]+right->res[j-1]);
                            }

                    }
                }
    }
}
}


и сам класс

class Node
{
public:
Node *parent;
Node *left;
Node *right;
int id;
int value;
int *res;};