题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
题目分析：
本题可以用递归和迭代来解答，那么就是要找规律了。因为青蛙只有 一次 1 阶或者 2 阶的跳法。
递归法：
1）当台阶为 1 时，只有一种跳法，一步到位。
2）当台阶为 2 时，有两种，一种是分两次跳，每次为 1；第二种，跳一次，一次跳两级；
3）从特殊推测到一般情况，假定第一次跳的是 1 阶，那么剩下的是 n-1 个台阶，跳法是 f(n-1);
4）假设第一次跳的是 2 阶，那么剩下的是 n-2 个台阶，跳法是 f(n-2)；
5）由 3）和 4）假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) ；
6）最终得出的是一个斐波那契数列：
| 1, (n=1)
f(n) = | 2, (n=2)
| f(n-1)+f(n-2) ,(n>2,n为整数)
额外补充：
直接找规律，f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5， 可以总结出f(n) = f(n-1) + f(n-2)的规律；
假设现在 6 个台阶，我们可以从第 5 跳一步到 6，这样的话有多少种方案跳到 5 就有多少种方案跳到 6；
另外我们也可以从 4 跳两步跳到 6，跳到 4 有多少种方案的话，就有多少种方案跳到 6，其他的不能从 3 跳到 6 什么的啦；
所以最后就是 f(6) = f(5) + f(4)；这样子也很好理解变态跳台阶的问题了。
public class Solution {
public int JumpFloor(int target) {
if (target <= 0) {
return -1;
} else if (target == 1) {
return 1;
} else if (target ==2) {
return 2;
} else {
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
}
迭代法：
public class Solution {
public int JumpFloor(int target) {
if(target <= 0) {
return 0;
}else if(target == 1) {
return 1;
}else if(target == 2) {
return 2;
}
int one = 1;
int two = 2;
int result = 0;
for(int i = 2; i < target; i++) {
result = one+ two;
one = two;
two = result;
}
return result;
}
}
参考文献：https://www.nowcoder.com/profile/214250/codeBookDetail?submissionId=1520111
