一 题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
二 解法1
1 分析
跳台阶问题是经典的递归问题，那么我们需要知道递归公式和递归终止条件。
1.1 递归公式
青蛙跳上n级台阶有两种情况可以实现，一是从n-1级台阶跳1级台阶、二是从n-2级台阶跳2级台阶，那么可以从中总结出递归公式为：f(n) = f(n-1) + f(n-2)。
1.2 递归终止条件
当只有1级台阶时，那么只有一种方法可以跳上；当有两级台阶时，那么就有两种方法了，一是一次跳两级，二是跳两次每次分别跳一级。所以f(1) = 1，f(2) = 2。
复杂度：时间复杂度O(n^2)，空间复杂度O(1)。
2 代码实现
1 class Solution { 2 public: 3 int jumpFloor(int number) { 4 if (number <= 0) return 0; 5 if (number == 1 || number == 2) return number; 6 7 return jumpFloor(number - 1) + jumpFloor(number - 2); 8 } 9 };
三 解法2
1 分析
类似于上一题中Fibonacci数列，更改为迭代。
复杂度：时间复杂度O(n)，空间复杂度O(1)。
2 代码实现
1 class Solution { 2 public: 3 int jumpFloor(int number) { 4 if (number <= 0) return 0; 5 if (number == 1 || number == 2) return number; 6 7 int lastValue = 2; //f(n-1)的值 8 int lastLastValue = 1; //f(n-2)的值 9 int ret; //返回值 10 for (int i = 3; i <= number; ++i) 11 { 12 ret = lastValue + lastLastValue; 13 lastLastValue = lastValue; 14 lastValue = ret; 15 } 16 17 return ret; 18 } 19 };
改篇博客为自己学习总结，水平有限，如有错误，欢迎交流！
原文：https://www.cnblogs.com/zpchya/p/11412700.html