Возникли проблемы при преобразовании из рекурсивного решения в DP

Question

Учитывая Двоичное дерево размера N, найдите в нем размер самого большого независимого набора (LIS). Подмножество всех узлов дерева является независимым, если между любыми двумя узлами подмножества нет ребра. Ваша задача - завершить функцию LISS (), которая находит размер самого большого независимого набора.

Я нашел это рекурсивное решение.

int rec(struct Node *root,bool t)
{
    if(root==NULL)
    return 0;

    if(t==true)
    {
        return max(1+rec(root->left,!t)+rec(root->right,!t),rec(root->left,t)+rec(root->right,t));
    }
    else
    {

        return max(rec(root->left,!t)+rec(root->right,!t),rec(root->left,t)+rec(root->right,t));
    }
}
int LISS(struct Node *root)
{
    int x,y;
    y=rec(root,true);

    return y;
}

Чтобы решить эту проблему с помощью DP Я изменил код следующим образом, но тогда он дает неправильный ответ. Он даже не работает с двоичным деревом с различными элементами.

map<int,int> mm;
int rec(struct Node *root,bool t)
{
    if(root==NULL)
    return 0;

    if(mm.find(root->data)!=mm.end())
    return mm[root->data];


    if(t==true)
    {
        mm[root->data]=max(1+rec(root->left,!t)+rec(root->right,!t),rec(root->left,t)+rec(root->right,t));
        return mm[root->data];
    }else
    {
        mm[root->data]=max(rec(root->left,!t)+rec(root->right,!t),rec(root->left,t)+rec(root->right,t));
        return mm[root-s>data];
    }
}
int LISS(struct Node *root)
{
    //Code here
    mm={};
    int y=0;

    y=rec(root,true);

    return max(x,y);
}

В чем ошибка?

Answer 1

В вашей функции два состояния, но вы запоминаете только одно состояние. Допустим, для root x,

rec(x,true) = 5 и

rec(x,false) = 10.

Вы сначала вычислили rec(x, true) и сохранили его на карте "мм" как мм [х] = 5.

Так что, когда вы пытаетесь получить значение rec(x, false), оно получает значение rec(x, true), которое составляет 5.