LeetCode 1137[第N个泰波那契数]
标题链接
LeetCode 1137[第N个泰波那契数]
详情
https://img2024.cnblogs.com/blog/3512406/202411/3512406-20241107194427259-1249777641.png
实例
实例1
https://img2024.cnblogs.com/blog/3512406/202411/3512406-20241107194433737-611005280.png
实例2
https://img2024.cnblogs.com/blog/3512406/202411/3512406-20241107194439208-491249541.png
提示
https://img2024.cnblogs.com/blog/3512406/202411/3512406-20241107194443746-2069646433.png
题解
思路一[递归]
当 n 为 0， 1， 2 时，直接返回对应的值
当 n 大于 2 时，开始用 f(n+3) = f(n) + f(n+1) + f(n+2) 来递归求值
代码一[此代码在力扣会超出时间限制]
class Solution {
public:
int tribonacci(int n) {
if (0 == n)
return 0;
if ((1 == n) || (2 == n))
return 1;
return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
}
};思路二[循环代替递归]
当 n 为 0， 1， 2 时，直接返回对应的值
当 n 大于 2 时，开始用 f(n+3) = f(n) + f(n+1) + f(n+2) 来递归求值
由于递归是不停的复制粘贴，在运行时必要大量的时间，当 n 数值过大时，就会超过力扣官方限制的时间
因此此处采用循环代替递归的方法
此处的循环体为： f(n+3) = f(n) + f(n+1) + f(n+2)
循环由 3 开始，由 n 结束，依次进入循环体求值，直到求出最后的 f(n) 的值并返回
代码二[此为成功代码]
class Solution {
public:
int tribonacci(int n) {
if (0 == n)
return 0;
if ((1 == n) || (2 == n))
return 1;
int a0 = 0, a1 = 1, a2 = 1;
int iRet = 0;
for (int i = 3; i < n + 1; i++)
{
iRet = a0 + a1 + a2;
a0 = a1;
a1 = a2;
a2 = iRet;
}
return iRet;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]