递归算法的记忆化

今天来搞一个递归算法。

有一只青蛙，一次能跳一级，也能跳两级，问跳n级台阶的时候，有几种方法？

这是一个很简单的递归，它的相应算法似乎也很容易，f(n) = f(n-1)+f(n-2)也就是说，他在第n级台阶跳的方法等于他在n-1级跳的次数加上n-2级跳的次数，于是递推关系式出来了，这个时候只要写出初始项也就是1级和2级的情况，代码也就写出来了

但是这个算法很有问题，运行数一多，它的运行时间会紧跟着往上走，比如说，当30级台阶的时候，它的运行时间为9秒！80级的时候，它就根本运行不出来了。。。。

所以这边重新引入一种新的算法，记忆化递归。

这名字听得高大上，其实核心就一个，我将每次递归运算得出的结果弄个数组存起来，这样下次直接用就好了，这是它对应的代码：

此时，我的每次上两级函数的值直接用自数组，不需要再重新进行计算，而这个算法对应30级台阶的时间为0毫秒，也就是一瞬间就算出来了，应该说变快了很多很多。

这就是今天介绍的记忆化递归算法，今后凡是遇到需要提高递归效能的，都可以使用记忆化递归算法。每天一个，强身健脑，明天见！