JZ69 跳台阶

描述

一只青蛙一次可以跳上1级台阶               ，也可以跳上2级               。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）
  
 
  
 
  
 
  
 
  
 
  
 
  
 
。 数据范围：1 \leq n \leq 401≤n≤40 要求：时间复杂度：O(n)O(n) 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
，空间复杂度： O(1)O(1)

方法1 递归

思路

题目分析













，假设f[i]表示在第i个台阶上可能的方法数













。 逆向思维 
  
  
  
  
  
  
  。如果我从第n个台阶进行下台阶 
  
  
  
  
  
  
  ，下一步有2中可能
  
  
  
  
  
  
  
，一种走到第n-1个台阶
 


 


 


 


 


 


 

，一种是走到第n-2个台阶
  
  
  
  
  
  
  
。 所以f[n] = f[n-1] + f[n-2] 
 
 
 
 
 
 
 ，那么初始条件了
   
   
   
   
   
   
   
，f[0] = f[1] = 1
 


 


 


 


 


 


 

。 所以就变成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1

代码

if(target == 0 || target == 1) return 1; return jumpFloor(target - 1) + jumpFloor(target - 2);

方法2 递归改进

思路

f(2)计算了两次
 

 

 

 

 

 

 
，f(1)计算了3次 

 

 

 

 

 

 

 ，f(0)计算了2次 
 
 
 
 
 
 
 。可以采用一个数组存储已经被计算过的值 此方法编译不通过              ，空间复杂度过高

代码

int[] f = new int[50]; if (target <= 1) return 1; if (f[target] != 0) return f[target]; return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));

方法3 动态规划

思路

思路：既然与斐波那契数列相同

 
 

 
 

 
 

 
 

 
 

 
 

 
 
，我们就把它放入数组中来解决
   
   
   
   
   
   
   
。 具体做法： step 1：创建一个长度为n+1的数组













，因为只有n+1才能有下标第n项                      ，我们用它记录前n项斐波那契数列
 

 

 

 

 

 

 
。 step 2：根据公式
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，初始化第0项和第1项 

 

 

 

 

 

 

 。 step 3：遍历数组




















，依照公式某一项等于前两项之和               ，将数组后续元素补齐
  
 
  
 
  
 
  
 
  
 
  
 
  
 
，即可得到fib[n]fib[n]fib[n]

代码

package esay.JZ69跳台阶; public class Solution { public static int jumpFloor(int target) { //方法1 /*if(target == 0 || target == 1) return 1; return jumpFloor(target - 1) + jumpFloor(target - 2);*/ //方法2 /*int[] f = new int[50]; if (target <= 1) return 1; if (f[target] != 0) return f[target]; return f[target] = (jumpFloor(target - 1) + jumpFloor(target - 2));*/ //方法3 if (target <= 1) return 1; int[] temp = new int[target + 1]; //初始化 temp[0] = 1; temp[1] = 1; //遍历相加 for (int i = 2; i <= target; i++) temp[i] = temp[i - 1] + temp[i - 2]; return temp[target]; } public static void main(String[] args) { System.out.println(jumpFloor(37)); } }