动态规划：自上而下与自下而上的比较

Question

你能给我指出一些自下而上比自上而下更有益的动态规划问题陈述吗？（即简单的 DP 工作更自然，但记忆会更难实现？）

我发现带有记忆的递归更容易，并且想要解决自下而上是更好/也许唯一可行的方法的问题。

我知道理论上两者是等效的，因此即使是易于实施之类的东西也会算作一个好处。

Answer 1

您将根据手头的问题应用自下而上的记忆法或自上而下的记忆法递归。

例如，如果您必须找到路径图的最小权重独立路径，您将使用自下而上的方法，因为您必须解决所有可能的子问题。

但是如果你必须解决背包问题，你可能想要使用递归自顶向下和记忆化，因为你必须解决有限数量的子问题。自下而上地处理背包问题会导致算法解决很多原始子问题中没有用到的冗余问题。