有用的算法技巧5.一些与递归相关的优化

5。一些与递归相关的优化

(1)。考虑可能递归的问题的状态保存

当我们使用递归来解决问题If时，很容易一遍又一遍地计算相同的子问题。这时候我们就需要考虑状态守恒，避免重复计算。例如，我随机问你一个我之前提出的问题

问题：青蛙一次可以跳1级或2级。青蛙能以多少种方式跳上 n 层楼梯？

这个问题很容易用递归解决。假设f(n)代表n步的总步数，则

f(n) = f(n-1) + f(n - 2)。

递归的结束条件是如果0