从递归解决方案到 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

您的函数中有两种状态，但您只记忆了一种状态。假设根 x，

rec(x,true) = 5 和

rec(x,false) = 10 .

您首先计算了 rec(x, true) 并将其作为 mm[x] = 5 保存在您的地图 "mm" 中。

因此，当您尝试获取 rec(x, false) 的值时，它获取的是 rec(x, true) 的值，即 5。

从递归解决方案到 DP 的转换有问题

Having problem in conversion from Recursive solution to DP

tree

recursion

binary-tree

dynamic-programming

c++14