树的最小顶点覆盖：动态规划公式

Question

我试图理解如何将寻找树的最小顶点覆盖的问题表述为一个动态规划问题，但遇到了一些麻烦。对我来说，涉及深度优先搜索的非动态规划公式具有最直观的意义。从本质上讲，这涉及到对叶节点进行DFS，包括最小大小顶点覆盖中的父节点，并重复到根节点。伪代码是这样的：

// DFS based solution
find_minimum_vertex_cover_dfs(root) {
    // leaf nodes aren't in minimum size vertex cover
    if (root == NULL || isLeafNode(root)) {
        return;
    }

    for (each child node of root) {
        find_minimum_vertex_cover_dfs(child node);
        // child isn't in minimum size vertex cover so need to cover edge
        // from current root to child by including current root
        if (!isInMinCover(child node)) {
            include root in minimum vertex cover;
        }
    }
}

我从这里得到的动态规划公式如下：

DynamicVC(root):
    for each child c:
        Best[c][0], Best[c][1] = DynamicVC(c)

    withoutRoot = sum over all c of Best[c][1]
    withRoot = 1 + sum over all c of min(Best[c][0], Best[c][1])

    return (withoutRoot, withRoot)

我想我理解子问题的思想是计算根植于每个顶点的子树的最小大小顶点复盖，包括复盖中的那个顶点，并从复盖中排除那个顶点。我有两个问题：

null

编辑：当我想的更多的时候，可能让我困惑的是，在这个例子中，递归地在树上做一个DFS是我更熟悉的。我已经做了很多动态规划问题，但这是第一个涉及树/图遍历的问题，在其他问题中，我可以使用一些循环来计算越来越大的子问题。我想我可以通过使用显式堆栈并以这种方式进行树遍历（而不是通过递归）来使动态编程版本更加熟悉。这有道理吗？

Answer 1

1：没有真正好的理由。它只是工作，所以为什么不使用它。对我来说，你所展示的DP解比递归解更直观。

2：动态规划是关于一个递归解的子问题的记忆。提出一个DP算法通常需要先定义一个递归，然后再给它添加记忆。递归解决方案可以自动转换为DP：只需创建(Subproblemid->result)类型的全局哈希表，并在递归调用开始时检查hashmap是否已经包含给定子问题的结果，如果是，则立即返回它，否则计算它并将其放入hashmap。这种方法通常与您提到的自下而上的方法一样快。