【前言】

今天是刷题打卡第52天！

今天是成为原创博主的第60天，一转眼马上两个月过去了鸭，坚持似乎也不是特别难的事，加油吧亲们。

原题： 斐波那契数列（记忆化搜索、简单DP）

题目链接：力扣

题目描述：

示例1：

  

   

    

     

    
    

     

      输入：2
     
    
   

    

     

    
    

     

      输出：1
     
    
   

    

     

    
    

     

      解释：F(2) = F(1) + F(0) = 1 + 0 = 1
     
    
  
 

示例2：

  

   

    

     

    
    

     

      输入：3
     
    
   

    

     

    
    

     

      输出：2
     
    
   

    

     

    
    

     

      解释：F(3) = F(2) + F(1) = 1 + 1 = 2
     
    
  
 

方法一：暴力递归

代码执行：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int fib(int n){
     
    
   

    

     

    
    

     
        //方法一：暴力递归
     
    
   

    

     

    
    

     
        //找边界
     
    
   

    

     

    
    

     
        if(n == 0){
     
    
   

    

     

    
    

     
            return 0;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        if(n == 1){
     
    
   

    

     

    
    

     
            return 1;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return fib(n - 1) + fib(n - 2);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

上面的代码存在的问题：

出现了大量的重复计算，比如： 

方法二：循环求解

代码执行：

【敲黑板】：需要注意对于循环体的书写，以及循环条件，可能不是我们想象中那样的平移过程。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int fib(int n){
     
    
   

    

     

    
    

     
        //方法二：循环解决
     
    
   

    

     

    
    

     
        int a = 0;
     
    
   

    

     

    
    

     
        int b = 1;
     
    
   

    

     

    
    

     
        int cur = 0;
     
    
   

    

     

    
    

     
        for(int i = 1; i <= n; i++)//当n为0时直接cur = 0
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  cur = a + b;
     
    
   

    

     

    
    

     

                  b = a;
     
    
   

    

     

    
    

     

                  a = cur;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return cur;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

方法三：记忆化搜索（简单DP）

思路：

即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int fib(int n){
     
    
   

    

     

    
    

     
        //方法三：记忆化搜索（简单DP）
     
    
   

    

     

    
    

     
        //找边界
     
    
   

    

     

    
    

     
        if(n == 0){
     
    
   

    

     

    
    

     
            return 0;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        if(n == 1){
     
    
   

    

     

    
    

     
            return 1;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        //需要定义一个大小为(n+1)的整形数组，并且初始化为0
     
    
   

    

     

    
    

     
        //之所以是n+1,是因为要使用到n这个下标
     
    
   

    

     

    
    

     
        vector<int> dp(n+1, 0);
     
    
   

    

     

    
    

     

              dp[0] = 0;
     
    
   

    

     

    
    

     

              dp[1] = 1;
     
    
   

    

     

    
    

     
        for(int i = 2; i < n+1; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  dp[i] = dp[i - 1] + dp[i - 2];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return dp[n];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

结语

今天是刷题打卡第52天！

加油吧少年。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121888470