当前位置：首页 > backend >正文

动态规划-1137.第N个泰波那契数-力扣(LeetCode)

backend 2025/5/9 3:19:14

一、题目解析

结合示例我们需要得出第i个泰波那契数的大小，由此我们能得出状态表示，dp[i]表示：第i个泰波那契数。

二、算法解析

根据题目要求我们得出了状态表示，对题目提供的定义式稍作变形就能得到状态转移方程。

原式为：Tn+3 = Tn + Tn+1 + Tn+2，将i替换n，并对下标减3

得到状态转移方程：Ti = Ti-1+ Ti-2 + Ti-3

初始化：根据题目我们需要初始化dp[0] = 0,dp[1] = dp[2] = 1即可，其余的可以通过定义式计算出来。

填表的顺序：例先填dp[4]，dp[4] = dp[3] + dp[2] + dp[1]，为了避免所需的状态未计算，所以从3开始从左到右依次填入数据进dp表中。

返回值：根据题目，我们只需要返回dp[i]的值即可。

老规矩，先根据上面的解析去自己实现，链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）

三、代码示例

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[0] = 0,dp[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];}
};

我们能知道时间复杂度是O(1),空间复杂度是O(N)，下面我们可以用滚动数组对其进行优化，使其空间复杂度为O(1).

四、空间优化

只需要在刚才代码的基础上，略加修改即可。

代码示例

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