剑指offer例题——跳台阶、变态跳台阶

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

思路：

n<=0时，有0种跳法

n=1时，只有一种跳法

n=2时，有两种跳法

已知当n>2时，当最后一次跳1级台阶，则之前有f(n-1)种跳法，当最后一次跳2级台阶时，之前有f(n-2)种跳法，即f(n)=f(n-1)+f(n-2);

故此处采用递归的方法

递归（英语：recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

 1 public class Solution {
 2     public int JumpFloor(int target) {
 3         if (target <= 0)
 4             return 0;
 5         if (target == 1)
 6             return 1;         
 7         if (target == 2)
 8             return 2;     
 9         return JumpFloor(target-1)+JumpFloor(target-2);
10     }
11 }

上述代码中，若去掉if语句的括号，则会产生缺失的错误

./Solution.java:3: error: '(' expected
if target == 0
^
./Solution.java:3: error: ')' expected
if target == 0
^
2 errors

待加入变态跳台阶，今天累了~

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

已知当青蛙第一次跳一级台阶，则之后有f(n-1)种跳法；

第一次跳两级台阶，则之后有f(n-2)种跳法；

第一次跳三级台阶，则之后有f(n-3)种跳法……第一次跳n级台阶，则有f(n-n)种跳法，故f(n)=f(n-1)+f(n-2)+……+f(n-n)，

同理f(n-1)=f(n-2)+……+f(n-n)。将上述两式相减，则f(n)-f(n-1)=f(n-1)，即f(n)=2*f(n-1)；

故上述编程为：

1 public class Solution {
2     public int JumpFloorII(int target) {
3         if (target<=0)
4             return 0;
5         if (target==1)
6             return 1;
7         return 2*JumpFloorII(target-1);
8     }
9 }

完美，最后结果为

运行时间：12ms；占用内存：9028k。

总结：递归是个好东西！