algorithm - 何时使用自下而上 DP 何时使用自上而下 DP

Question

我学过这两种DP方式，现在很迷茫。不同情况下我们如何选择？而且我发现在大多数情况下，自上而下对我来说更自然。谁能告诉我如何做出选择。

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

Answer 1

为简单起见，我将根据我对一些sources的总结进行解释。

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，可以避免堆栈溢出。