迭代，自下而上，分而治之算法

Question

我正在阅读此LeetCode article，了解一个常见的算法问题“最长的公共前缀”。它们显示了几种不同的方法，但是我的问题仅与“分而治之”有关。它的示例显示了您经常在各处的书籍和博客中看到的典型的递归自顶向下方法。

[考虑到这一点，我认为我应该能够“迭代”地并且“自下而上”地进行此操作。类似自底向上的合并排序方法。所以这就是我的结局：

// type "Stack", function "prefix", and "min" implementations are not shown for brevity.
// Just assume they're defined somewhere and they work correctly.
//
// "prefix" function accepts two strings and returns a string
// Examples:
// prefix("abcd", "ab") returns "ab"
// prefix("abcd", "efgh") returns ""
// ... you get the idea.
//
// "min" does exactly what you'd expect. Its arguments are both type int.
func lcpDAndC(a []string) string {
        n := len(a)

        if n == 0 {
                return ""
        }

        var (
                stack Stack
                p, q  string
        )
        for lo := 0; lo < n; lo += 2 {
                hi := min(lo+1, n-1)
                stack = stack.Push(prefix(a[lo], a[hi])
        }

        for stack.Len() > 1 {
                p, q = stack.Pop2()
                stack.Push(prefix(p, q))
        }

        return stack.Pop1()
}

所以我的问题是：这是否仍被认为是“自下而上”和“分而治之？”我认为可以安全地假设立即从叶子开始（自下而上的部分）可以是一次处理两个元素的问题，因为它一次穿过数组（“除” ...也可以“征服？ ”）。当然，这里的堆栈与递归方法中的调用堆栈起着同等的作用。虽然，队列也能正常工作，这是我认为我已经走出深渊的另一个原因。

如果这不是“自下而上”和“分而治之”的适当应用，那么这是否至少适用了我不知道的其他理论？

Answer 1

本文中使用的递归是Top Down，因为它们将较大的案例分解为较小的案例，然后合并较小案例的结果。

在递归中，函数调用彼此叠加到函数调用堆栈上。它们都弹出

(1) Once the base case is reached

或

(2) Results of function calls above them in the stack has been computed and it's their turn now.

您的代码不执行Bottom Up递归，也不是D&C，

考虑这种情况：-

[“” care“，” car“，” cat“，” cater“，” click“，” clang“，” core“，” coral“]

初始堆栈：-

cor
cl
cat
car

同时循环迭代＃1：

c
cat
car

同时循环迭代＃2：

c
car

同时循环迭代＃3：

c

您的while循环以串行方式组合元素，并且不使用D&C的属性。如果将for循环中的lo+=2更改为lo+=1，则您的代码与Approach 1: Horizontal scanning相同。

但是，使用队列会使代码成为Bottom-Up递归。请注意，每次弹出两个元素时，它们都代表两个互斥的一半，这些一半也可以在Top Down方法的递归树中找到。考虑这种情况：-

[“” care“，” car“，” cat“，” cater“，” click“，” clang“，” core“，” coral“]

最初排队：-

cor
cl
cat
car

同时循环迭代＃1：

ca
cor
cl

同时循环迭代＃2：

c
ca

同时循环迭代＃3：

c