何时使用自下而上DP，何时使用自顶向下DP。

Question

我已经采用了两种方式的DP，但我现在感到困惑。我们在不同的情况下如何选择？我发现在大多数情况下，自上而下对我来说更自然。有人能告诉我如何做出选择吗。

PS:我读过这篇文章，旧员额，但仍然感到困惑。需要帮助。不要认为我的问题是重复的。我曾说过，两者是不同的。我希望知道如何选择和何时从自上而下或自下而上的方式考虑问题。

Answer 1

为了简单起见，我将根据一些资料来源的总结进行解释。

1. 自上而下:看起来像：a(n) = a(n-1) + a(n-2)。有了这个等式，您就可以通过使函数a调用自己来实现大约4到5行代码。正如您所说，它的优势对大多数开发人员来说是非常直观的，但是执行它需要更多的空间(内存堆栈)。
2. 自下而上:首先是计算a(0)，然后是a(1)，然后将其保存到某个数组(例如)，然后继续保存a(i) = a(i-1) + a(i-2)。使用这种方法，您可以显著提高代码的性能。使用大型n，可以避免堆栈溢出。

Answer 2

一个稍长一点的答案，但我试图解释我自己的方法，动态编程，以及我在解决这些问题后已经理解了什么。我希望未来的用户发现它有帮助。请随时评论和讨论：

在考虑动态规划问题时，自顶向下的解决方案更自然。你从最终的结果开始，试着找出你能达到目标的方法。例如，对于fib(n)，我们知道我们只能通过fib(n-1)和fib(n-2)到达这里。因此，我们再次递归调用函数来计算这两种情况的答案，这将越来越深入到树中，直到达到基本情况为止。然后构建答案，直到所有的堆栈被弹出，我们才得到最终的结果。

为了减少重复计算，我们使用一个缓存，它存储一个新的结果，并在函数试图再次计算它时返回它。所以，如果你想象一棵树，函数调用不需要一直到叶子，它已经有了答案，所以它会返回它。这被称为回忆录，通常与自上而下的方法相联系。

现在，我认为自下而上方法的一个重要要点是，您必须知道最终解决方案的构建顺序。在自上而下的情况下，你只需要把一件事分解成很多东西，但是在自下而上的情况下，你必须知道从一个层次到另一个层次需要参与计算的状态的数量和顺序。在一些简单的问题上(如。谎言(N)，这是很容易看到的，但是对于更复杂的情况，它并不是自然的。我通常遵循的方法是自上而下地思考，将最后的情况分解为以前的状态，并试图找到一个模式或顺序，然后能够将其重新构建起来。

关于何时选择这两种状态，我建议采用上面的方法来确定这些状态之间的相互关系和正在建立的状态。通过这种方法，您可以找到一个重要的区别，即实际需要多少计算，以及有多少计算可能是多余的。在自下而上的情况下，在进入下一个级别之前，您必须填充整个级别。但是，在自顶向下的情况下，如果不需要，可以跳过整个子树，这样就可以节省大量额外的计算。

因此，选择显然取决于问题，也取决于国家之间的相互关系。通常情况下，推荐自下而上，因为与递归方法相比，它节省了堆栈空间。然而，如果你觉得递归不是太深，而是非常广泛，并可能导致许多不必要的计算表格化，然后你可以采取自上而下的方法与回忆录。

例如，在这个问题：https://leetcode.com/problems/partition-equal-subset-sum/中，如果您看到讨论，就会提到自顶向下比自下而上更快，基本上，使用缓存的二叉树方法相对于背包自下而上的构建更快。我把它作为理解两国关系的一个练习。

Answer 3

自下而上和自顶向下的DP方法对于许多问题在时间和空间复杂性方面是相同的。区别在于，自下而上的速度要快一点，因为你不需要递归的开销，当然，自上而下更直观和自然。

但是，自上而下方法的真正优势可以是在一些小任务集上，在这里，您不需要计算所有较小的子任务的答案！在这种情况下，你可以减少时间的复杂性。

例如，您可以使用自上而下的方法和记忆来寻找N-斐波纳契数，其中序列被定义为an=an-1+an-2，因此，您有两个O(N)时间来计算它(我没有与O(logN)解比较来找到这个数字)。但是看看序列an=an/2+an/2-1有一些小N的边缘情况，在botton方法中，你不能比O(N)更快地完成它，在O(N)中，自顶向下的算法将与复杂度O(logN)一起工作(或者可能是一些多对数复杂度，我不确定)。