本文主要是介绍Leetcode刷题详解——第 N 个泰波那契数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目链接：1137. 第 N 个泰波那契数
2. 题目描述：
泰波那契序列 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。
3. 解法（动态规划）
3.1 算法流程：
-
状态表示：
dp[i]表示：第i个泰波那契数的值 -
状态转移方程：
dp[i]=dp[i-1]+dp[i-2]+dp[i-3] -
初始化：
将
0，1，2位置的值初始化。题目中已经告诉我们dp[0]=0,dp[1]=dp[2]=1 -
填表顺序：
从左往右
-
返回值：
返回
dp[n]的值
3.2 c++算法代码：
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];}
};
这篇关于Leetcode刷题详解——第 N 个泰波那契数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
