《剑指offer》第10题跳台阶

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

思路1：递归暴力解法
n级有f(n) 种方法，要么跳一步，要么跳两步。假如此时跳一步，那么剩余n-1就有f(n-1) 种方法，如果跳两步，那么剩余n-2就有f(n-2) 种方法。则f(n) = f(n-1) + f(n-2)。
再考虑n=1和n=2的特殊情况 f(1) = 1，f(2) = 2。
```
public class Solution {
 public int JumpFloor(int target) {
     if (target < 1) {
         return 0;
     }
     if (target == 1 || target == 2) {
         return target;
     }
     return JumpFloor(target - 1) + JumpFloor(target - 2);
 }
}
```
思路2 也称记忆化搜索法注意和递归一样是自顶而下，从n分析到1
观察f(n) = f(n-1) + f(n-2)
以及f(n-1) = f(n-2) + f(n-3)。发现f(n-1)和f(n)在调用递归时，都会用到f(n-2)，此时f(n-2)就重复计算了，因此当n足够大时，效率会降低，因此需要优化，以减少重复的计算。
优化思路就是，f(n-2)只计算一次，并且在初次计算过后，我就记录下来，当你要用时，直接拿结果，而不用再次调用递归f(n-2) = f(n-3) + f(n-4)进行计算。
因此设计如何记录结果，就变成了思路2的重点,首先我们建一个数组，用来存放计算过的值，本示例的代码是将该数组所有元素赋值为-1，接着进入判断，如果你是初始值-1，那么你可以调用递归计算（为初始值说明没有赋值也就是没有进行过递归计算），然后将结果赋值给数组，如果你算过了（已经赋值过了），那就不用算了，直接返回当前的值。（ps：赋值为-1是因为该数列的所有结果集不可能出现-1的情况）
由于有n阶台阶，意味着从1阶到n阶有n个值需要存放在数组。因此数组的实际使用的是arr[1]到arr[n]，考虑到初始传入的target可能为0，因此创建的数组长度最好是target+1,否则会报数组越界的错误
```
public class Solution {

 public int JumpFloor(int target) {
    int[] arr = new int[target+1];//创建数组赋值
     for(int i =0;i<=target;i++){
         arr[i]=-1;
     }
     return fib(target,arr);
 }
 public int fib(int target,int[] arr){ 
     if (target < 1) {
         return 0;
     }
     if (target == 1 || target == 2) {
         return target;
     }
     if(arr[target] == -1 ){//如果等于，说明没算过，允许递归调用计算，并将结果赋值
         arr[target] =fib(target - 1,arr) + fib(target - 2,arr);
     }
     return arr[target]; //如果不等于，说明已经计算过，直接返回。
 }
}
```

思路3 又是大名鼎鼎的动态规划这里是自下而上的思路
说白了，三级的走法和一二级的走法有关，四级的和二三级的走法有关，那我从小算到大，一步一步一直算到n不就好了，这样根本用不到递归，而且算法的复杂度也不高。
先用数组的方式实现，利用数组来记录计算过程中要用到的值

public class Solution {

 public int JumpFloor(int target) {
    int[] arr = new int[target+1];//为了防止越界 只是这里可以不用赋初值l
     return fib(target,arr);
 }
 public int fib(int target,int[] arr){ 

     if(target==0) return arr[0]=0;  //上面防了，这里也要防越界，不能给角标为1和2的赋值
     if(target==1) return arr[1]=1;  
     if(target==2) return arr[2]=2;
    //只有防止传入参数target为0，1，2的情况下，才能赋这两个特殊值
     arr[1] =1;
     arr[2] =2;
     for(int i=3;i<=target;i++){
         arr[i] = arr[i-1]+arr[i-2];
     }    
     return arr[target];
 }
}

这里不使用数组的情况下再做一次，这里不使用数组的时候，需要观察到一个规律，比如
f(5)=f(4)+f(3)
|| ||
f(6)=f(5)+f(4)
首先我必须用result变量记录结果，但是上一个结果f(5)我在下一次计算的时候用到了，而且算f(5)的f(4)也用到了，相当于只淘汰了f(3)，因此我需要两个变量来记录新的值，这与数组的思路不同，上面的数组需要开辟较大空间，而本方法只用到了三个变量，进行循环使用。所以减少了空间复杂度。

public class Solution {

 public int JumpFloor(int target) {
     int first = 1;
     int second = 2;
     int result = 0;
     if(target==0) return 0; 
     if(target==1) return 1; 
     if(target==2) return 2; 
     for(int i = 3; i <= target; i++) {
         result = second+first;     //f(5)=f(4)+f(3) 
         first = second;            //重新赋值，代替原本f(3)位置的数
         second = result;           //重新赋值，代替原本f(4)位置的数
     }
     return result;
 }
}

《剑指offer》第10题 跳台阶

《剑指offer》第10题跳台阶