📘 題目敘述
Tribonacci 序列 Tn 定義如下：
T0 = 0，T1 = 1，T2 = 1- 並且對於
n >= 0：T(n+3) = Tn + T(n+1) + T(n+2)
給你一個整數 n，請回傳 Tn 的值。
條件限制
0 <= n <= 37- 答案保證可以放進 32-bit 有號整數
🧠 解題思路
這題就是直接照遞推式做 DP。
我用一個陣列 t 存每一項 Tribonacci 的值：
- 先把初始值放好：
t[0]=0、t[1]=1、t[2]=1 - 之後從
i = 3開始往上推：t[i] = t[i-3] + t[i-2] + t[i-1]
最後回傳 t[n]。
這樣做的重點是：每一項只需要前面三項，從小算到大就能得到答案。
所有變數
t：DP 陣列，t[i]存Ti的值i：用來從 3 推到n的迴圈索引
🪜 主要流程步驟
1. 建立陣列 t 並放入初始值
我先建立 int t[38]，因為題目 n <= 37，開到 38 足夠。
接著把 t[1] = 1、t[2] = 1 設好（t[0] 會保持 0）。
2. 用遞推式從 i = 3 推到 n
我用 for 迴圈從 i = 3 到 n：
t[i] = t[i-3] + t[i-2] + t[i-1]
每一步都只用到前面三項。
3. 回傳 t[n]
迴圈結束後，t[n] 就是答案。
⏱️ 複雜度
- 時間複雜度：
O(n) - 空間複雜度：
O(1)，因為t的大小是固定 38，不會隨 n 成長
💻 程式碼實作
class Solution {
public:
int tribonacci(int n) {
int t[38] = {0};
t[1] = 1, t[2] = 1;
for (int i = 3; i <= n; i++) {
t[i] = t[i - 3] + t[i - 2] + t[i - 1];
}
return t[n];
}
};
🔗 題目連結
https://leetcode.com/problems/n-th-tribonacci-number/