编程：跳台阶问题

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

 1 public class solution {
 2 
 3     public static int jumpfloor(int target) {
 4         if(target <=0)
 5             return 0;
 6         if(target ==1)
 7             return 1;
 8         if(target==2)
 9             return 2;
10         int one = 1;
11         int two = 2;
12         int result = 0;
13         for(int i = 2; i < target; i++){
14             result = one+ two;
15             one = two;
16             two = result;
17         }
18         return result;
19     }
20 }

对于每次只跳1/2个台阶的情况来说：

1.假设第一次跳1个台阶，则剩下n-1个台阶的所有跳法数f(n-1);

2.假设第一次跳2个台阶，则剩下n-2个台阶的所有跳法数f(n-2);

3.在此特定条件下，可以判断出符合斐波那契数列规律；

4.f(1)=1;f(2)=2;以此进行f(n)=f(n-1)+f(n-2)的计算；

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

  public class solution {
      public int jumpfloorii(int target) {
                  if(target<1)
              return 0;
          if(target==1)
              return 1;
          int num=0;
          for(int i=1;i<target;i++) {
              num+=jumpfloorii(target-i);
          }
          return num+1;
      }
  }

 

1. 整体思路与第一个问题一致：将f(n)的问题转化为f(n-1)、f(n-2)……的问题
2. 本题采取递归方法；
3. 返回num+1的问题尚待补充；