03 | 备忘录：如何避免递归中的重复计算？
什么是重叠子问题？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了递归中的重复计算问题及其解决方法——备忘录的应用。作者以斐波那契数列和硬币找零问题为例，说明了递归中重复计算的问题所在，并通过具体的代码实现和图示清晰地展示了如何使用备忘录来解决这一问题。文章还总结了重叠子问题处理模式和重叠子问题缓存的限制，为读者提供了解决指数级时间复杂度问题的重要思路。通过本文的阐述，读者可以快速了解递归中的重复计算问题及备忘录的应用，为动态规划问题的解决提供了重要思路。备忘录的思想极为重要，特别是当求解的问题包含重叠子问题时，只要面试的问题包含重复计算，你就应该考虑使用备忘录来对算法时间复杂度进行简化。含有备忘录的递归算法已经与动态规划思想十分相似了，从效率上说也是如此。备忘录让我们实现了对算法时间复杂度的“降维打击”，这与贪心算法到递归的进步程度不同，这是真正意义上的动态规划思维。记住使用备忘录来优化你的算法时间复杂度，它是提高算法效率的高级手段。
《动态规划面试宝典》，新⼈⾸单¥59
全部留言(22)
- 最新
- 精选
webmin递归是分治处理问题的方法分为两部分：递和归，递是自上而下，分解问题，归是自下而上收集计算处理结果。如果要反过来就会变成先收集计算结果后分解问题在逻辑上是矛盾的。 另把递归改为迭代方式，也是在用stack或queue等模拟压栈和出栈，用在堆上分配内存的方式解决栈大小限制的问题，本质还是自上而下的。作者回复: 没错。递归算法始终是自上而下的，这是由其算法特性决定的。
2020-09-19228
osun递归只能自顶向下，不能自底向上，如果要实现可以借助栈数据结构作者回复: 对～
2020-09-186
追风筝的人F(x)=H(G(V(F(S(x,c)),c)) 好像每个问题都能用函数表达，函数即正义作者回复: 此刻，我特别想把开篇词那张图改一改，放在这！函数即正义～
2020-10-194
pearl刘东洋F(x)=H(G(V(F(S(x,c)),c))这个函数是不是少了一个右括号？作者回复: 火眼金睛！是的，已纠正。
2021-04-132
3.141516
递归等价于 f(n) 和 f(n - 1) 之间的方程描述，即要想知道 n 需要知道 n - 1，在逻辑上是不可逆的。哪怕你写出了 f(n - 1) 和 f(n) 的方程描述，前提是题目编程知道 n，求解 1，所以实际上还是一种自上而下的。作者回复: 动态规划其实是通过自下而上解决递归问题的重复计算问题，你从整个问题结构去看肯定还是自上而下的，动态规划只不过是调整了计算顺序。
2021-05-101
宋不肥有了缓存，其实就是在最末尾位置上找可以往前一步范围内的最优质值，其实就是一步范围的贪心，但前序的所有缓存值都是前序的全局最优解了，所以一步贪心就是全局最优解！所以这样倒推的贪心就是动态规划，由已有的全局最优解贪心到最后所求全局的最优解，是一种递推的方式，所以wiki上dp的翻译其实是利用分治的动态递推！分治这里其实就是贪心！利用递归实现而已！所以加上回溯的贪心递推就是DP！终于自己把逻辑理顺了！比较难的好课还是得二刷三刷才能完全理解熬！作者回复: 应该这样说，DP里肯定是用到了和贪心类似的“根据当前情况“求解”下一步的最优解“的思路。只不过DP是在分析问题的性质和结构后定义了一个正确的”贪心“函数，确保每一步的贪心（局部最优解）得到的就是这种状况下的全局最优解，只不过求解顺序肯定是自下向上而已。同时又利用缓存避免重复计算。
2020-10-281- Paul Shan老师能否举一个关于下面描述的例子，多谢！ 有些问题虽然看起来像包含“重叠子问题”的子问题，但是这类子问题可能具有后效性，但我们追求的是无后效性。所谓无后效性，指的是在通过 A 阶段的子问题推导 B 阶段的子问题的时候，我们不需要回过头去再根据 B 阶段的子问题重新推导 A 阶段的子问题，即子问题之间的依赖是单向性的。
作者回复: 理解非常正确！赞
2020-09-2421 
无隅这个f(n)的分解树图要是能横过来就好啦（不过我怀疑是不是横过来放不下 ，所以展示成上下形式）作者回复: 嗯嗯，对的～
2022-08-10归属地：上海
全麦小面包先考虑子问题的个数，我只画了这颗树的一部分，因此从树上这个比较难看出来，但从斐波那契数列的题目上我们可以推广，得到其个数是 O(nm), m=|values|，即指数级别；再考虑求解一个子问题的复杂度：每个子问题中含有一个循环，因此时间复杂度为 O(m), m=|values|；综上所述，该算法的时间复杂度是 O(mnm), m=|values|。 这里的mn是什么？n不能简单地用总金额替代吧？否则n=10000,m={1000,5000}，这个时间复杂度不是爆炸？最好能明确地指出它们的含义，感谢！作者回复: 这里m是总额的数量，n是面值的数量。时间复杂度是做规模估计，所以实际上不会有那么多次（每次从0遍历到m），但是这个是不影响时间复杂度的规模的（这个维度上只会有常数级别的缩减），的确是“爆炸”。
2021-09-01
空想家min(f(x−c)+1),x>0,f(x−c)=−1,c∈C0,x=0−1,x<0 这个怎么理解呢作者回复: x是总额，C是面值的集合，c表示从C集合中取面值，min(f(x-c)+1)表示从C中取出所有的c，然后取f(x-c)+1的最小值作为f(x)的值。
2021-08-25
