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. 状态显示
2. 状态转移方程
3. 初始化（防止填表时不越界）
4. 填表顺序
5. 返回值

1.状态表示

2.状态转移方程

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);
    }
};