LeetCode刷题--- 第 N 个泰波那契数

本文主要是介绍LeetCode刷题--- 第 N 个泰波那契数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

http://t.csdnimg.cn/yUl2I

【C++】

http://t.csdnimg.cn/6AbpV

数据结构与算法

http://t.csdnimg.cn/hKh2l

前言：这个专栏主要讲述动态规划算法，所以下面题目主要也是这些算法做的

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

第 N 个泰波那契数

题目链接：第 N 个泰波那契数

题目

泰波那契序列 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。

解法

题目解析

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2。
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

算法原理讲解

我们这题使用动态规划，我们做这类题目可以分为以下五个步骤

状态显示
状态转移方程
初始化（防止填表时不越界）
填表顺序
返回值

1.状态表示

这道题可以【根据题⽬的要求】直接定义出状态表示：

dp[i] 表示：第 i 个泰波那契数的值。

2.状态转移方程

题⽬已经⾮常贴⼼的告诉我们了：

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

3.初始化

从我们的递推公式可以看出， dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的，因为 dp[-2] 或 dp[-1] 不是⼀个有效的数据。
因此我们需要在填表之前，将 0, 1, 2 位置的值初始化。题⽬中已经告诉我们 dp[0] = 0, dp[1] = dp[2] = 1 。

4.填表顺序

毫⽆疑问是「从左往右」。

5.返回值

应该返回 dp[n] 的值。

代码实现

时间复杂度：O(n)。
空间复杂度：O(1)。

一、使用一维数组

class Solution {
public:int tribonacci(int n) {if (n == 0 || n == 1) return n;vector<int> dp(n + 1);dp[0] = 0;dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; 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 || n == 1) return n;int p = 0, q = 0, r = 1, s = 1;for (int i = 3; i <= n; ++i) {p = q;q = r;r = s;s = p + q + r;}return s;}
};

三、递归（超时）

class Solution {
public:int tribonacci(int n) {if (n == 0 || n == 1) return n;if (n == 2)return 1;return tribonacci(n-1) + tribonacci(n-2) + tribonacci(n-3);}
};