《剑指offer》面试题10：题目2跳台阶（C++实现）

题目描述思路一：简单的递归思路二：用数组记录f(n)思路三：自底向上计算（动态规划）小结参考文献

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

问题分析： 1.如果台阶数小于等于0 返回0。 2.如果台阶数等于1 咱们的小青蛙有1种跳法。 3.如果台阶数等于2 咱们的小青蛙有2种跳法： （1）一次跳2级楼梯。 （2）分两次跳，一次跳1级楼梯。

4.如果台阶数为n ，不妨用f(n)表示n级楼梯的跳法。 （1）咱们的第一步如果跳1级楼梯，此时的跳法数目和后面的n-1级楼梯的跳法数目相同。即f(n-1) （2）咱们的第一步如果跳2级楼梯，此时的跳法数目和后面的n-2级楼梯的跳法数目相同。即f(n-2) 这里咱们就会得到一个关系f(n)=f(n-1)+f(n-2)

咦？！这不那谁吗？ 这不就是那斐波那契数列吗？我滴龟龟。 不过不一样的地方是，它的函数表达式不太一样。 $$f(n)=\{\begin{array}{rlr}0& & \text{n=0}\\ 1& & \text{n=1}\\ 2& & \text{n=2}\\ f(n-1)+f(n-2)& & \text{n>2}\end{array}$$ 博主之前写过一篇很详细的，用三种思路解决的斐波那契数列的博客，链接贴在这里。 link. 以下解决青蛙跳楼梯的思路，也是和上面这篇博客的大同小异。

思路一：简单的递归

根据上面的思路分析，n<=2我们列情况解决即可。 n>3我们采用递归解决。 所以我们很快能写出如下的代码：

//运行时间：528ms //占用内存：620k class Solution { public: int jumpFloor(int number) { int result[3]={0,1,2}; if(number<3) return result[number]; return jumpFloor(number-1)+jumpFloor(number-2); } };

很好，说明你还记得以前学的东西。但是我们现在是要马上去面试的人了，怎么能写这么low的代码呢？ 说它low是因为上述的代码有很严重的递归问题，比如求解f(10)，你需要求解f(9)和f(8）。而求解f(9),你又需要去求解f(8)和f(7)。 说到这里，你会发现上面的f(8)咱们就求解了两遍！如果是一个特别大的数字，那么重复求解的问题会呈指数级的急剧增加，所以我们得想个法子，把这个重复求解的问题把它解决了！

思路二：用数组记录f(n)

最简单的思路，就是用一个数组来记录下我们的f(n),每次计算f(n)前，我们先查询这个值是否计算过，如果没有，就执行递归调用计算它，并把它存储下来，下次直接调用就可以了。 如果有，那就更好了，咱们不用客气，直接拿来用，这样就省去了很多重复求解的问题。

//运行时间：3ms //占用内存：476K class Solution { public: int jumpFloor(int number) { int memo[50]={-1}; for(int i=0;i<3;i++) memo[i]=i; for(int i=3;i<=number;i++) memo[i]=memo[i-1]+memo[i-2]; return memo[number]; } };

思路三：自底向上计算（动态规划）

既然可以用递归实现，我们自然可以想到用动态规划去实现。 首先根据f(0)和f(1)去推算f(2),再根据f(1)和f(2)去推算f(3),依次类推，直到推算出我们要求的f(n)，再把这个值返回即可。

//运行时间：4ms //占用内存：480K class Solution { public: int jumpFloor(int number) { int result[3]={0,1,2}; if(number<3) return result[number]; int FibMinusTwo = 1;//定义f(n-1) int FibMinusOne = 2;//定义f(n-1) int FibN= 0; for(int i=3;i<=number;i++){ FibN = FibMinusOne + FibMinusTwo;//f[i]=f[i-1]+f[i-2]; FibMinusTwo = FibMinusOne;//更新f[i-2]; FibMinusOne = FibN;//更新f[i-1]; } return FibN; } };

相对于思路二而言，思路三更加节省空间。

小结

思路一代码会有很多重复计算的地方，不太可靠。 思路二应用了memo来记录，避免了思路一里面很多重复计算的地方。 思路三相对于思路二而言，在占用内存上又有了更好的优化。

整体而言，思路三最佳。

参考文献

《剑指offer》

牛课网刷题链接link.