由于题目类似，这里总和一下，并进行拓展
目录
1.跳台阶
2.变态跳台阶
3.拓展篇——疯魔版跳台阶
题目一：
题目二：
1.跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
题目分析：
一共n级，跳两级当n>2时，假设函数 f(n) 表示总共跳法数，那么此时下一级跳 1 级，剩下的跳法数就是 f(n-1)，如果跳两级那么剩下就是 f(n-2)；此时出现等式 f(n) = f(n-1) + f(n-2)；问题就变成了斐波那契数列问题。
如不懂斐波那契数列问题，可看 https://blog.csdn.net/weixin_42513339/article/details/88927290，实际本质就是动态规划算法。
程序如下：
class Solution {
public:
int jumpFloor(int number) {
if(number == 0)
return 0;
else if(number == 1)
return 1;
else if(number == 2)
return 2;
else{
int a1 = 1, a2 = 2,count = 2;
while(count != number)
{
int m = a2;
a2 = a1+a2;
a1 = m;
count++;
}
return a2;
}
}
};
递归版
class Solution {
public:
int jumpFloor(int number) {
if (number == 0) return 0;
else if (number == 1) return 1;
else if (number == 2) return 2;
else
return jumpFloor(number-2)+jumpFloor(number-1);
}
};
2.变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
代码如下：
class Solution {
public:
int jumpFloorII(int number) {
if (number == 0) return 0;
else if (number == 1) return 1;
else{
return 2 * jumpFloorII(number - 1);
}
}
};
3.拓展篇——疯魔版跳台阶
题目一：
有了前两个跳台阶的思想 ，我们可以再换个想法，假设题目如下：
一只青蛙一次可以跳上2级台阶，也可以跳上3级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：跟第一个思路很类似，只是不能跳1级，那么我们应该可以得到一个类似的公式，即：f(n) = f(n-2)+f(n-3)，我们可以举例：
那么如果两级台阶，只有一种跳法。
如果三级台阶，只有一种跳法，如果四级台阶，那么也是只有一种跳法，如果是五级台阶，到了五级，我们终于用到上面的公式了，即 f(5) = f(3)+f(2)； 我们再举例，如果六级，那么就是f(6) = f(4)+f(3)，七级 f(7) = f(5) = f(4)等等，我们都可以用这个公式表示，所以代码就好写了。如下：
int jumpFloor3(int n) {
if(n<=1) return 0;
if(n==2 || n==3 || n==4)
return 1;
return jumpFloor3(n-2)+jumpFloor3(n-3);
}
题目二：
一只青蛙一次可以跳上1级台阶，也可以跳上2级，也可以跳上3级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：还是改版题目，我们只需要写出 f(1) = 1, f(2) = 2, f(3) = 4,即可创建等式，即：f(n) = f(n-1)+f(n-2)+f(n-3)。
int jumpFloor4(int n) {
if(n <= 0) return 0;
if(n == 1) return 1;
if(n == 2) return 2;
if(n == 3) return 4;
return jumpFloor4(n-1)+jumpFloor4(n-2)+jumpFloor4(n-3);
}
类似题目有很多，主要还是需要熟悉这种递归方法，当然动态规划来做个人感觉好一点，青蛙跳台阶和斐波那契数列都是动态规划入门的题目，需要好好掌握，所以我这里多写了点。
