第N个泰波那契数

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值

动态规划（dp数组）：

class Solution {
public:int tribonacci(int n) {// 创建dp数组，大小为n+1，用于存储泰波那契数列的前n项vector<int> dp(n + 1);// 边界条件1：当n=0时，直接返回0（泰波那契数列定义）if (n == 0)return 0;// 边界条件2：当n=1或n=2时，直接返回1（泰波那契数列定义）if (n < 3)return 1;// 初始化dp数组的前3项（泰波那契数列的起始值）dp[0] = 0;  // 第0项为0dp[1] = 1;  // 第1项为1dp[2] = 1;  // 第2项为1// 从第3项开始迭代计算，直到第n项for (int i = 3; i < n + 1; i++) {// 泰波那契数列定义：第i项 = 前3项之和dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}// 返回第n项的结果return dp[n];}
};

优化：（空间O（n）->O(1)）:

class Solution {
public:int tribonacci(int n) {// 边界条件1：当n=0时，直接返回0（泰波那契数列定义）if (n == 0)return 0;// 边界条件2：当n=1或n=2时，直接返回1（泰波那契数列定义）if (n < 3)return 1;// 初始化变量，存储最近3项的结果：// a 表示第 i-3 项（初始为 trib(0) = 0）// b 表示第 i-2 项（初始为 trib(1) = 1）// c 表示第 i-1 项（初始为 trib(2) = 1）int a = 0, b = 1, c = 1;// 从第3项开始迭代计算，直到第n项for (int i = 3; i < n + 1; i++) {// 计算当前项：第i项 = 前3项之和（trib(i) = trib(i-1) + trib(i-2) + trib(i-3)）int d = a + b + c;// 更新变量，为下一轮计算做准备：// a 移动到原来的 b（即 i-2 项变为 i-3 项）a = b;// b 移动到原来的 c（即 i-1 项变为 i-2 项）b = c;// c 移动到当前计算的 d（即当前项变为 i-1 项）c = d;}// 循环结束后，c 中存储的就是第n项的结果return c;}
};