在 n-ary 树中找到最大非相邻和的算法

Question

给定一棵 n 元整数树，任务是找到一个子序列的最大和，其约束条件是序列中的任何 2 个数字都不应共享树中的公共(public)边。例子: 1个 /\ 2 5 /\ 3 4最大非相邻和 = 3 + 4 + 5 = 12以下是 http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent 中概述的算法的错误扩展？

def max_sum(node, inc_sum, exc_sum):
    for child in node.children:
        exc_new = max(inc_sum, exc_sum)
        inc_sum = exc_sum + child.val
        exc_sum = exc_new
        inc_sum, exc_sum = max(max_sum(child, inc_sum, exc_sum),
                               max_sum(child, inc_sum, inc_sum - node.val))
    return exc_sum, inc_sum

但我不确定在返回时交换 exc_sum 和 inc_sum 是否是获得结果的正确方法，以及我如何跟踪可能导致最大和的可能总和，在这个例子中，最大总和左子树是 (1+3+4) 而导致最终最大值的和是 (3+4+5)，那么应该如何跟踪 (3+4)？是否应该将所有中间金额存储在一个表中？

Answer 1

假设 dp[u][select] 存储答案:最大子序列总和，没有两个节点有边，这样我们只考虑以节点 u< 为根的子树/strong>(这样 u 是否被选中)。现在你可以编写一个递归程序，其中每个递归的状态是 (u,select) 其中 u 表示正在考虑的子图的根和 select> 表示我们是否选择节点 u。于是我们得到如下伪代码

     /* Initialize dp[][] to be -1 for all values (u,select) */
     /* Select is 0 or 1 for false/true respectively        */

     int func(int node , int select )
     {
         if(dp[node][select] != -1)return dp[node][select];
         int ans = 0,i;

         // assuming value of node is same as node number
         if(select)ans=node;

         //edges[i] stores children of node i
         for(i=0;i<edges[node].size();i++)
         {
             if(select)ans=ans+func(edges[node][i],1-select);
             else ans=ans+max(func(edges[node][i],0),func(edges[node][i],1));
         }
         dp[node][select] = ans;
         return ans;
     }

     // from main call, root is root of tree and answer is
     // your final answer
     answer = max(func(root,0),func(root,1));

除了递归之外，我们还使用了记忆化来降低时间复杂度。它在空间和时间上都是O(V+E)。你可以在这里看到一个工作版本代码 Code 。单击右上角的 fork 以在测试用例上运行
4 1
1 2
1 5
2 3
2 4
它按预期提供输出 12。
输入格式在代码的注释中指定以及其他说明。它在 C++ 中，但如果你想在 python 中理解代码，则不会有重大变化。如果您对代码有任何疑问，请发表评论。