N-th Tribonacci Number

題目描述

Tribonacci 數列定義：T(0)=0, T(1)=1, T(2)=1，T(n) = T(n-1) + T(n-2) + T(n-3)（n ≥ 3）。給定 n，回傳 T(n)。

輸入：n = 4
輸出：4
解釋：T(4) = T(3) + T(2) + T(1) = 2 + 1 + 1 = 4

輸入：n = 25
輸出：1389537

解題思路

初始化

t0=0, t1=1, t2=1，對應 T(0)、T(1)、T(2) 三個基礎值

滾動計算

從 i=3 到 n，計算 next = t0 + t1 + t2。例如 i=3 時 next = 0+1+1 = 2

更新變數

t0 ← t1, t1 ← t2, t2 ← next，三個變數像窗口一樣往右滑動一格

回傳結果

迴圈結束後 t2 就是 T(n)。若 n ≤ 2 則直接回傳初始值（0 或 1）

程式碼

C#

csharp

public class Solution {
    public int Tribonacci(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        
        int t0 = 0, t1 = 1, t2 = 1;
        for (int i = 3; i <= n; i++) {
            int next = t0 + t1 + t2;
            t0 = t1;
            t1 = t2;
            t2 = next;
        }
        return t2;
    }
}

TypeScript

typescript

function tribonacci(n: number): number {
    if (n === 0) return 0;
    if (n <= 2) return 1;
    
    let [t0, t1, t2] = [0, 1, 1];
    for (let i = 3; i <= n; i++) {
        const next = t0 + t1 + t2;
        [t0, t1, t2] = [t1, t2, next];
    }
    return t2;
}

Python

python

def tribonacci(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    
    t0, t1, t2 = 0, 1, 1
    for _ in range(3, n + 1):
        t0, t1, t2 = t1, t2, t0 + t1 + t2
    return t2

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

Time：從 3 到 n 線性遍歷一次，每步只做一次加法和三次賦值
Space：只用三個滾動變數，不隨 n 增長（相比用陣列的 O(n) 方案大幅節省）

圖解

t0 = 0

+→

t1 = 1

+→

t2 = 1

+→

next = t0+t1+t2

更新→

滾動：t0←t1←t2←next

圖表展示了滾動變數的運作方式：三個變數加總得到 next，然後整體右移一格。這是 DP 空間優化的經典技巧——當狀態只依賴有限個前驅時，不需要保留整個 DP 陣列。

進階觀點

💡面試追問

滾動變數的核心思想是什麼？ T(n) 只依賴 T(n-1)、T(n-2)、T(n-3)，計算完 T(n) 後 T(n-3) 不再被需要。所以用三個變數輪流覆蓋，將空間從 O(n) 降到 O(1)。這個技巧適用於所有「狀態只依賴常數個前驅」的 DP 題。
n 非常大（如 10^18）怎麼辦？ 用矩陣快速冪：T(n) 的遞推可以表示為矩陣乘法 [[1,1,1],[1,0,0],[0,1,0]]^(n-2) × [T(2),T(1),T(0)]^T，矩陣冪可以用快速冪在 O(log n) 完成。
為什麼 Tribonacci 是 DP 入門的好題？ 它展示了 DP 三大核心：定義狀態（T(n)）、寫出轉移方程（前三項和）、空間優化（滾動變數），而且沒有複雜的決策邏輯。

邊界情況

n 等於 0：直接回傳 0，不進入迴圈
n 等於 1 或 2：直接回傳 1，不進入迴圈
n 等於 37（題目上限）：T(37) = 2082876103，仍在 32 位整數範圍內（2^31 - 1 ≈ 21.5 億）

理解測驗

🤔 為什麼只需要三個變數而不是一個陣列？

🤔 如果改用遞迴（不加 memoization）計算 T(n)，時間複雜度是多少？