你怎么知道什么时候应该使用备忘录？

Question

我正在学习记忆化，虽然我在Python中需要时实现它没有问题，但我仍然不知道如何确定需要它的情况

我知道它是在子载波重叠时实现的，但是如何确定是否是这种情况？一些递归函数似乎在进行重叠调用之前就已经深入。你会如何在编码面试中识别这一点？您是否会列出所有调用（即使其中一些调用在O（2^n）复杂度暴力解决方案中深入5-6级）

像斐波那契序列这样的情况是有意义的，因为重叠会立即发生（“fib（i-1）”调用几乎会立即与“fib（i-2）”调用重叠。但在其他情况下，比如背包问题，我仍然不知道任何人在面试时应该如何使用回忆录。有没有快速检查重叠的方法

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

Answer 1

为了实现“记忆化”解决方案，您首先需要确定问题中的以下两个属性：

1. 重叠子问题
2. 最优子结构

看来你明白了。第（2）款：

Optimal Substructure: If the optimal solution to a problem, S, of size n can be calculated by JUST looking at optimal solution of a subproblem, s, with size < n and NOT ALL solutions to a subproblem, AND it will also result in an optimal solution for problem S, then this problem S is considered to have optimal substructure.

有关更多详细信息，请查看以下答案：

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