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

时间:2022-12-10 17:54:28

时间限制:1秒     空间限制:32768k

斐波那契数列指的是这样一个数列: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368。

可以观察到,从第3个数开始,每个数的值都等于前连个数之和。

同时,定义f(0)=0, f(1)=1.

则 f(2)=f(1)+f(0)=1;

  f(3)=f(2)+f(1)=2;

  ... 依次类推,

  f(n)=f(n-1)+f(n-2)

该问题实质是斐波那契数列求和,递推公式为 f(n)=f(n-1)+f(n-2);

可以考虑,小青蛙每一步跳跃只有两种选择:一是再跳一级阶梯到达第 i 级阶梯,此时小青蛙处于第 i-1 级阶梯;或者再跳两级阶梯到达第 i 级阶梯,此时小青蛙处于第 i-2 级阶梯。

于是,i 级阶梯的跳法总和依赖于前 i-1 级阶梯的跳法总数f(i-1)和前 i-2 级阶梯的跳法总数f(i-2)。因为只有两种可能性,所以,f(i)=f(i-1)+f(i-2);

依次类推,可以递归求出n级阶梯跳法之和。

递归算法实现:

public int JumpFloor(int target){

  if(target<0)

    return 0;

  int[] fib={0,1,2};

  if(target<3)

    return fib[target];

  return JumpFloor(target-1)+JumpFloor(target-2);

}

备注:此方法不满足空间要求(递归空间)。

非递归算法:

public int JumpFloor(int target){

  if(target<0)

    return 0;

  int[] fib={0,1,2};

  if(target<3)

    return fib[target];

  int total=0;

  int firstElem=1;

  int secondElem=2;

  for(int i=3;i<=target;i++){

    total=firstElem+secondElem;

    firstElem=secondElem;

      secondElem=total;  //迭代

  }

  return total;

}

转自:http://www.nowcoder.com/questionTerminal/f4d47027d49a48b28274f6d4e0b6ff79?pos=12&tagId=0&orderByHotValue=1