您能否指出一些自下而上比自上而下更有益的动态编程问题陈述？（即简单的 DP 更自然地工作，但记忆化会更难实现？）
我发现使用记忆的递归要容易得多，并且希望解决自下而上是更好/也许唯一可行的方法的问题。
我知道理论上两者都是等价的，所以即使是易于实现之类的东西也可以算作好处。
问问题
4050 次
2 回答
7
您将根据手头的问题应用自下而上的记忆或自上而下的记忆递归。
例如，如果您必须找到路径图的最小权重无关路径，您将使用自下而上的方法，因为您必须解决所有可能的子问题。
但是如果你必须解决背包问题，你可能想使用递归自上而下的记忆，因为你必须解决有限数量的子问题。自下而上处理背包问题将导致算法解决许多原始子问题中未使用的冗余问题。
于 2013-01-13T06:30:13.907 回答
3
决定使用哪种算法时要考虑的两件事
- 时间复杂度。两种方法通常具有相同的时间复杂度，但因为 for 循环比递归函数调用便宜，如果以机器时间来衡量，自底向上可以更快。
- 空间复杂性。（在自顶向下时不考虑额外的调用堆栈分配）通常两种方法都需要为所有子解决方案建立一个表，但自底向上遵循拓扑顺序，它的辅助空间成本有时可以减少到问题的大小直接依赖。例如：
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)，我们只需要存储过去的两次计算
话虽如此，自下而上并不总是最好的选择，我将尝试举例说明：
- （@Nikunj Banka 提到）自上而下仅解决您的解决方案使用的子问题，而自下而上可能会在冗余子问题上浪费时间。一个愚蠢的例子是0-1 背包和 1 件物品......运行时间差是 O(1) 与 O(重量)
- 您可能需要执行额外的工作才能获得自下而上的拓扑顺序。在Matrix 中的最长增加路径中，如果我们想在它们的依赖关系之后处理子问题，我们必须按降序对矩阵的所有条目进行排序，这是
nmlog(nm)DP 之前的额外预处理时间
于 2017-12-06T08:26:00.593 回答