【前言】

今天是刷题打卡第60天！

一起加油啦兄弟们。

原题：第N个泰波那契数（记忆化搜索、简单DP） 

原题链接：力扣 

题目描述：

示例1：

  

   

    

     

    
    

     

      输入：n = 4
     
    
   

    

     

    
    

     

      输出：4
     
    
   

    

     

    
    

     

      解释：
     
    
   

    

     

    
    

     

      T_3 = 0 + 1 + 1 = 2
     
    
   

    

     

    
    

     

      T_4 = 1 + 1 + 2 = 4
     
    
  
 

 示例2：

  

   

    

     

    
    

     

      输入：n = 25
     
    
   

    

     

    
    

     

      输出：1389537
     
    
  
 

代码执行：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    int tribonacci(int n) {
     
    
   

    

     

    
    

     
        //找边界
     
    
   

    

     

    
    

     
        if(n == 0)
     
    
   

    

     

    
    

     
            return 0;
     
    
   

    

     

    
    

     
        if(n == 1 || n == 2)
     
    
   

    

     

    
    

     
            return 1;
     
    
   

    

     

    
    

     
        //定义一个大小为n+1的整形数组，并将其初始为0
     
    
   

    

     

    
    

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

    

     

    
    

     

              dp[0] = 0;
     
    
   

    

     

    
    

     

              dp[1] = 1;
     
    
   

    

     

    
    

     

              dp[2] = 1;
     
    
   

    

     

    
    

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

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];//递推公式
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return dp[n];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      };
     
    
  
 

结语

今天是刷题打卡第60天！

加油吧少年。

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

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