【手把手带你刷好题】—— 60.第N个泰波那契数(记忆化搜索、简单DP)

举报
安然无虞 发表于 2022/05/26 22:56:35 2022/05/26
【摘要】 【前言】 今天是刷题打卡第60天! 一起加油啦兄弟们。 原题:第N个泰波那契数(记忆化搜索、简单DP)  原题链接:力扣  题目描述:   示例1: 输入:n = 4输出:4解释:T_3 = 0 + 1 + 1 = 2T_4 = 1 + 1 + 2 = 4 &nb...

【前言】

今天是刷题打卡第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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。