你怎么知道什么时候应该用回忆录？

Question

我正在学习关于回忆录的知识，虽然在Python需要的时候实现它没有什么困难，但我仍然不知道如何确定需要它的情况。

我知道，当存在重叠子调用时，它是实现的，但是如何确定是否是这种情况呢？在进行重叠调用之前，有些递归函数似乎变得很深。在一次编码面试中，你会如何识别这一点？你会画出所有的调用(即使其中的一些调用在O(2^n)复杂的蛮力解决方案中达到5-6级)吗？

像Fibonacci序列这样的情况是有意义的，因为重叠会立即发生( 'fib(i-1)‘调用几乎会立即与'fib(i-2)’调用重叠)。但在其他情况下，比如背包问题，我仍然无法思考如何在面试时使用回忆录。有没有快速检查重叠的方法？

我希望我的问题有意义。如果有人能给我一个好的资源，或者给我线索去寻找，我会非常感激的。提前谢谢。

Answer 1

为了达到“回忆录”解决方案，您首先需要确定问题中的以下两个属性：

subproblems

• Optimal重叠

1. 子结构

看来你确实明白(1)。第(2)款：

最优子结构:如果一个子问题S的最优解s

关于更多细节，请看以下答案：

https://stackoverflow.com/a/59461413/12346373