【力扣】1137. 第n个泰波那契数

原题链接：. - 力扣（LeetCode）

目录

1. 题目描述

2. 思路分析

3. 代码实现

---

1. 题目描述

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

2. 思路分析

dp。

1. 状态表示：dp[i]表示第i个泰波那契数的值。（状态表示就是是什么的意思，也就是dp表里面的值所表示的含义）

2. 状态转移方程：dp[i]=dp[i-3]+dp[i-2]+dp[i-1]  （将 n-3代入题目给的 Tn+3 = Tn + Tn+1 + Tn+2 这个式子得到）

3. 初始化：dp[0]=0,dp[1]=dp[2]=1（这一步是为了保证填dp表的时候不越界）

4. 填表顺序：从左向右（为了填写当前状态的时候，所需要的状态计算过了）

5. 返回值：因为题目要求的是第n个泰波那契数，所以返回dp[n]即可

空间优化——使用滚动数组

我们求dp[4]时，只需要知道dp[1]，dp[2]，dp[3]的值即可，此时dp[0]这个元素的空间相当于浪费了；同理我们求dp[5]时，只需要知道dp[2]，dp[3]，dp[4]这三个元素，此时dp[0]和dp[1]这两个元素的空间相当于浪费了。此时我们就可以用滚动数组进行优化，滚动数组也可以运用到dp中经典的背包问题。

3. 代码实现

处理一些边界情况（因为0<=n<=37，当n==0时，此时相当于vector<int> dp(1），dp[1]和dp[2]就越界了，所以我们需要特判。)

1. 创建dp表

2. 初始化

3. 填表

4. 返回值

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;i++){ //填表
            dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
        }
        return dp[n];  //返回值
    }
};

使用滚动数组进行空间优化后的代码

class Solution { 
public:              
    int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        int a=0,b=1,c=1,d=0;
        for(int i=3;i<=n;i++){
            d=a+b+c;
            a=b;b=c;c=d;
        }
        return d;
    }
};