02.跳台阶问题

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码
• 04.题目延申
• 05.延申问题分析
• 06.示例代码

01.题目要求

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

02.问题分析

2.1 正常分析法

• a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);
• b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)
• c.由a，b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)
• d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

2.2 找规律分析法

• 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)；这样子也很好理解变态跳台阶的问题了。
• 所以这道题其实就是斐波那契数列的问题代码只需要在上一题的代码稍做修改即可。和上一题唯一不同的就是这一题的初始元素变为 1 2 3 5 8.....而上一题为1 1 2 3 5 .......。另外这一题也可以用递归做，但是递归效率太低，所以这里只给出了迭代方式的代码。

03.实例代码

• 代码如下所示

  int jumpFloor(int number) {
  	if (number <= 0) {
  		return 0;
  	}
  	if (number == 1) {
  		return 1;
  	}
  	if (number == 2) {
  		return 2;
  	}
  	int first = 1, second = 2, third = 0;
  	for (int i = 3; i <= number; i++) {
  		third = first + second;
  		first = second;
  		second = third;
  	}
  	return third;
  }

04.题目延申

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

05.延申问题分析

• 假设n>=2，第一步有n种跳法：跳1级、跳2级、到跳n级

  跳1级，剩下n-1级，则剩下跳法是f(n-1)
  跳2级，剩下n-2级，则剩下跳法是f(n-2)
  ......
  跳n-1级，剩下1级，则剩下跳法是f(1)
  跳n级，剩下0级，则剩下跳法是f(0)
  所以在n>=2的情况下：
  f(n)=f(n-1)+f(n-2)+...+f(1)
  因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
  所以f(n)=2*f(n-1) 又f(1)=1,所以可得**f(n)=2^(number-1)**

06.示例代码

• 代码如下所示

  int JumpFloorII(int number) {
  	return 1 << --number;//2^(number-1)用位移操作进行，更快
  }

• java中有三种移位运算符：

  1. “<<” :**左移运算符**，等同于乘2的n次方
  2. “>>”:**右移运算符**，等同于除2的n次方
  3. “>>>” **无符号右移运算符**，不管移动前最高位是0还是1，右移后左侧产生的空位部分都以0来填充。与>>类似。
  例：
  int a = 16;
  int b = a << 2;//左移2，等同于16 * 2的2次方，也就是16 * 4
  int c = a >> 2;//右移2，等同于16 / 2的2次方，也就是16 / 4