本文主要是介绍剑指offer：青蛙跳台阶I 青蛙跳台阶 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
I 题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：
斐波那契数列变体，关键是找出递推公式。
假设跳n级台阶有f(n)中跳法，容易发现f(1)=1,f(2)=2; n>2时，如果最后一次跳一级台阶，一共有f(n-1)种跳法，如果最后一次跳两级台阶，一共有f(n-2)种跳法。即f(n)=f(n-1)+f(n-2)。
代码：
在线测试OJ：
https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&tqId=11161&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
AC代码：
class Solution {
public:
//循环int jumpFloor(int number) {if(number <= 0)return 0;if(number == 1)return 1;if(number == 2)return 2;int n_1 = 2;int n_2 = 1;int f_n;for(int i = 3; i <= number; i++){f_n = n_1 + n_2;n_2 = n_1;n_1 = f_n;}return f_n;}
};II 题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
斐波那契数列变体，关键是找出递推公式。
同样的思路，但是递推公式变为，f(1)=1,f(2)=2,f(n)=1+f(1)+f(2)+...+f(n-2)+f(n-1)，由f(n-1)=1+f(1)+f(2)+...+f(n-2)，两式相减可得，f(n)=2f(n-1),n>=3。用数学归纳法可以证明，f(n)=2^(n-1)。
代码：
在线测试OJ：
https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
AC代码：
class Solution {
public:int jumpFloorII(int number) {if(number <= 0)return 0;if(number == 1)return 1;if(number == 2)return 2;int n_1 = 2;int f_n;for(int i = 3; i <= number; i++){f_n = 2*n_1;n_1=f_n;}return f_n;}
};
这篇关于剑指offer：青蛙跳台阶I 青蛙跳台阶 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
