algorithm - 树的最小顶点覆盖 : Dynamic Programming Formulation

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;
        }
    }
}

我从 here 得到的动态规划公式如下:

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)

我想我理解子问题的想法是计算以每个顶点为根的子树的最小顶点覆盖，包括覆盖中的那个顶点，并从覆盖中排除那个顶点。我有两个问题:

1. 利用叶节点永远不会处于最小顶点覆盖这一事实对我来说似乎是最自然的，因此使用基于 DFS 的解决方案。为什么要使用动态规划解决这个问题？
2. 我习惯于自下而上地迭代构建动态规划矩阵，而不实际使用递归。然而，在这种情况下，因为我需要从计算叶节点的解决方案开始，使用递归从叶节点向上构建动态编程矩阵遍历树对我来说似乎是最直观的。这对我来说似乎很奇怪，因为到目前为止我处理的所有动态编程问题都避免了对此的需要。我在这里遗漏了什么吗？

编辑:当我考虑更多时，也许让我感到困惑的是，在这种情况下，递归地在树上执行 DFS 对我来说更熟悉。我一直在做一堆动态规划问题，但这是第一个涉及树/图遍历的问题，在其他问题中，我可以只使用一些循环来计算越来越大的子问题。我想我可以通过使用显式堆栈并以这种方式而不是通过递归来进行树遍​​历，从而使我更熟悉动态编程版本。这有意义吗？

Answer 1

1:没有很好的理由。它只是工作所以为什么不使用它。对我来说，您展示的 DP 解决方案比递归解决方案更直观。

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