青蛙跳台阶问题详解递归思想

迷南。 2022-11-21 11:24 156阅读 0赞

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

输入1
    返回值1

示例2:

输入4
    返回值5

思想： 经典递归问题
    思路：跳n级台阶相当于n-1和n-2级台阶的和
    原因：n级台阶就相当于n-1级再跳一次一阶的和n-2级再跳一次2阶的
    
    
    
    
    public class Solution {
        
        public int JumpFloor(int n) {
        
         if (n == 1) return 1;
            if (n == 2) return 2;
            return JumpFloor(n - 1) + JumpFloor(n - 2);
        }
    }

优化后的代码：

public class Solution {
        
       //使用哈希map ,充当备忘录
            Map<Integer,Integer> tempMap=new HashMap();
            public int JumpFloor(int n) {
        
                //n=0 也算一种
                if(n == 0) return 1;
                if(n<=2) return n;
                //先判断有没有计算过，即看看备忘录有没有
                if(tempMap.containsKey(n)){
        
                    //备忘录中有，即计算过，直接返回
                    return tempMap.get(n);
                }else{
        
                    //备忘录中没有，即没有计算过，执行递归计算 并把结果保存至备忘录
                    tempMap.put(n,JumpFloor(n-1)+JumpFloor(n-2));
                    return tempMap.get(n);
                }
                
        }
    }

优化的原因：

递归存在的问题

递归调用层级太多，导致栈溢出问题  
递归重复计算，导致效率低下  
栈溢出问题

每一次函数调用在内存栈中分配空间，而每个进程的栈容量是有限的。  
当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。  
其实，我们在前面小节也讨论了，递归过程类似于出栈入栈，如果递归次数过多，栈的深度就需要越深，最后栈容量真的不够咯  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center]  
要计算原问题 f(10)，就需要先计算出子问题 f(9) 和 f(8)  
然后要计算 f(9)，又要先算出子问题 f(8) 和 f(7)，以此类推。  
一直到 f(2) 和 f(1），递归树才终止。

**我们先来看看这个递归的时间复杂度吧，「递归时间复杂度 = 解决一个子问题时间\*子问题个数」**

一个子问题时间 = f（n-1）+f（n-2），也就是一个加法的操作，所以复杂度是 「O(1)」；  
问题个数 = 递归树节点的总数，递归树的总结点 = 2n-1，所以是复杂度「O(2n)」。

因此，青蛙跳阶，递归解法的时间复杂度 = O(1) \* O(2^n) = O(2^n)，就是指数级别的，爆炸增长的，「如果n比较大的话，超时很正常的了」。

回过头来，你仔细观察这颗递归树，你会发现存在「大量重复计算」，比如f（8）被计算了两次，f（7）被重复计算了3次…所以这个递归算法低效的原因，就是存在大量的重复计算！

**「那么，怎么解决这个问题呢？」**

既然存在大量重复计算，那么我们可以先把计算好的答案存下来，即造一个备忘录，等到下次需要的话，先去「备忘录」查一下，如果有，就直接取就好了，备忘录没有才再计算，那就可以省去重新重复计算的耗时啦！这就是「带备忘录的解法」

我们来看一下「带备忘录的递归解法」吧~

一般使用一个数组或者一个哈希map充当这个「备忘录」。

假设f(10)求解加上「备忘录」，我们再来画一下递归树：

「第一步」，f（10）= f(9) + f(8)，f(9) 和f（8）都需要计算出来，然后再加到备忘录中，如下：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center 1]  
「第二步，」 f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因为 f(8) 已经在备忘录中啦，所以可以省掉，f(7),f（6）都需要计算出来，加到备忘录中~![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center 2]  
「第三步，」 f(8) = f（7）+ f(6),发现f(8)，f(7),f（6）全部都在备忘录上了，所以都可以剪掉。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/301877a8a1934bdca10537b406045ba4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201031232758785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201031232843859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201031232922795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoYXNzZA==,size_16,color_FFFFFF,t_70#pic_center