当前位置: 首页> 科技> 能源 > 重庆公司大学派斯学院_店铺logo图片免费_在线代理浏览国外网站_南宁seo费用服务

重庆公司大学派斯学院_店铺logo图片免费_在线代理浏览国外网站_南宁seo费用服务

时间:2025/7/10 17:30:52来源:https://blog.csdn.net/weixin_65043441/article/details/143466063 浏览次数:0次
重庆公司大学派斯学院_店铺logo图片免费_在线代理浏览国外网站_南宁seo费用服务

题目描述:

泰波那契序列 Tn 定义如下: 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:

输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2:

输入:n = 25
输出:1389537

提示:

  • 0 <= n <= 37
  • 答案保证是一个 32 位整数,即 answer <= 2^31 - 1

题目链接:

. - 力扣(LeetCode)

解题主要思路:

妥妥的动态规划,需要注意的是泰波那契数是从0开始,因此第n个泰波那契数,我们需要开的空间是n+1个。

不过,做完后发现,我们始终是只需要四个int变量,因此我们可以采用滚动数组的方式来进行空间优化。

解题代码:

(非优化版本)

class Solution {
public:int tribonacci(int n) {if (n == 0) return 0;if (n == 1 || n == 2) return 1;vector<int> dp(n+1);  // dp表dp[0] = 0, dp[1] = dp[2] = 1;  // 初始化for (int i = 3; i < n+1; ++i) {dp[i] = dp[i-1] + dp[i-2] + dp[i-3];}return dp[n];}
};

(空间优化 -- 滚动数组版本)

class Solution {
public:int tribonacci(int n) {if (n == 0) return 0;if (n == 1 || n == 2) return 1;int a, b, c, dst;  // 四个int类型变量来代替dp表a = 0, b = c = 1;  // 初始化for (int i = 3; i < n+1; ++i) {dst = a + b + c;a = b, b = c, c = dst;}return dst;}
};

关键字:重庆公司大学派斯学院_店铺logo图片免费_在线代理浏览国外网站_南宁seo费用服务

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: