在二叉树中查找一组 "k"标记顶点的算法，该算法最小化所有节点到标记祖先的距离

Question

这是我原来的问题:

我需要设计一个如上所述的算法。
我不确定该怎么做。
我知道应该始终标记根节点，否则成本将是无限的。
我想我应该以某种方式使用动态规划。
我不确定如何将问题分解为子问题。

Answer 1

如下创建一个具有三个变量的动态状态

func( index of node(ind),
      how many nodes can be colored in this subtree(k),
      distance to closest marked ancestor(d) )

现在对于每个状态，您可以像这样计算出最佳结果:

if node is leaf
    if k>0 // if we can mark this node the distance will be 0
        return 0
    return d
result = infinity

// if this node is not marked yet, and we can mark it, mark it
if d != 0 and k > 0 
    result = min(result, func(ind, k-1, 0)
for t=0 to k
    // dedicate t mark nodes to left child and k-t mark nodes to right child
    result = min(result, func(index of left_child, t, d+1) + 
                         func(index of right_child, k-t, d+1) +
                         d )
return result // sum of the distances of this node and its descendants to the closest marked node

打电话

func(0, // root index
     k,
     infinity)

会给你最好的结果。

您可以将每个状态的结果保存在内存表中，以将此解决方案转换为动态方法。