何时使用自下而上的 DP 以及何时使用自上而下的 DP

Question

我已经学过DP的两种方式，但现在我很困惑。不同情况下我们该如何选择？我发现大多数时候自上而下对我来说更自然。谁能告诉我如何做出选择。

PS：我已经读过这篇旧文章，但仍然感到困惑。需要帮忙。不要将我的问题视为重复。我已经提到过它们是不同的。我希望知道如何选择以及何时以自上而下或自下而上的方式考虑问题。

Answer 1

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

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