2019-03-14 跳台阶

题目出自《剑指offer》，整理自https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

1. 问题

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

2. 思路

首先我选择的是循环，每次有跳1个台阶或2个台阶的可能，然后减去跳过的台阶，但是接下来就没有思路了。
于是又考虑递归，考虑分治法，考虑第一次跳有2种方法，第二次又有两种。考虑到边界条件,递归外边的target = 1，target = 2 这两种情况就分别返回1，2即可

      //特殊情况
        if(target == 1){
            return 1 ;
        }
        
        if(target == 2){
            return 2;
        }
        
        return getNum(target);

重点来看下递归体,重要部分我暂时没放出来，终止条件很好理解，就是只剩1和2的情况，直接返回1和2

  public int getNum(int target){
        if(target == 1){
            return 1;
        }else if(target == 2){
            return 2;
        }else{
            return ？？？？？;
        }
    }

对于 ？？？？？ 部分，我一开始写的是。

2 * getNum(xxx);

显然不对，xxx不知道要传什么了，是传target - 1 还是 target - 2？无解，
结合刚才所提到的分治法，我们的目的就是把大问题划分成小问题去求解，
我们第一次跳1个台阶，那么接下来就剩target - 1 的台阶，对于target - 1就是一个子问题，我们逐步缩小规模，直到最后产生最小的子问题，剩1个，或者剩2个。

那这样分析过后，就显得清楚了许多，我写了如下内容

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

思考递归，千万不要刨根问底。
思考递归，千万不要刨根问底。
思考递归，千万不要刨根问底。

这是一个忠告，站在宏观的角度上理解递归，懵不懵逼是程序自己的事儿，不是程序猿的事儿，作为一个程序猿，你只需要在大局下知道你这个语句是求了个啥，你就不害怕递归了。

上面的求了个啥？
为啥这样写，还不是因为我们思考上一个代码的时候，传参不会写了？
那么既然-1也不合适，-2也不合适，分成两块好了。

第一块求如果是-1 是啥情况呢？
第二块求如果是-2 是啥情况呢？

相加，Perfect,所有的情况都包含了。

但一旦你试图去理解，-1是怎么运行的，子问题还得-2 ，balabala……
那么恭喜你已经进入了下面这个状态！

如果你说了，你上面讲的宏观 我才做不到呢，你给我讲讲怎么运行的！
好好好，那我就给你画图说一说吧。

image.png

瞧瞧，瞧瞧，这优雅的画技。

首先target = 5进入递归，调用getNum(target - 1) 与 getNum(target - 2)
产生了4和3两个子问题，4和3说，我不知道答案，我去问问我孩子。

然后产生了3，2 和2，1，同样他们3说我也不知道，我得去问我孩子，而其他的都说我知道，分别返回了自己的值。

最后3也找到了它的孩子2，1，分别返回了自己的值。

那么问题来了，值是多少？
刚才说了，2是返回2的，1是返回1的，
你数数树杈子，看看到底是几嘛！

什么还不懂？
斐波那契数列了解一下。

3.完整代码

public static int JumpFloor(int target) {
    
     
      if(target == 1){
          return 1 ;
      }
      
      if(target == 2){
          return 2;
      }
      
      return getNum(target);
  }
  
  
  public static int getNum(int target){
      if(target == 1){
          return 1;
      }else if(target == 2){
          return 2;
      }else{
          return getNum(target - 1) + getNum(target - 2);
      }
  }

4. 运行

先去吃饭，吃完饭更！

仔细看上面的递归树，会发现有很多重复的调用

由此看来性能也不会很好，所以我们就要考虑循环版本了。
https://www.nowcoder.com/profile/214250/codeBookDetail?submissionId=1520111

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        int one = 1;
        int two = 2;
        int result = 0;
        for(int i = 2; i < target; i++){
            result = one+ two;
            one = two;
            two = result;
        }
        return result;
    }
}

for循环内，是不断更新斐波那契数的过程。

两种算法的算法复杂度分析如下：

递归算法：

二叉树的高度是 n - 1，由我们的基础知识可以知道，一个高度为k的二叉树最多可以由 2^k - 1个叶子节点，也就是递归过程函数调用的次数，所以时间复杂度为 O(2^n)，而空间复杂度就是树的高度 S(n)

循环算法：

时间：O(n)
空间：O(1)

5. 结束

结束了，没啥说的，最近复习复试很焦躁，月底就要结束这煎熬了，这一年很充实，希望复试成功吧！