泰波那契数 图解题解

泰波那契数到底在算什么

泰波那契数列和斐波那契长得像，只是把「前两项相加」换成「前三项相加」。它从 T0=0、T1=1、T2=1 起头，之后每项都等于紧挨它的前三项之和。给你 n，求第 n 项 T(n)，比如 n=10 时答案 149。

为什么照定义递归会算不完

照定义写递归 T(n)=T(n-1)+T(n-2)+T(n-3)，会摊成一棵疯狂分叉的树：算 T(n-1) 时又把 T(n-2)、T(n-3) 重算一遍，越往下重复越离谱，时间随 n 指数膨胀。

根子是同一个 T(k) 被反复重算。既然每项只由更小的项决定，反过来从 T0 一个个往上填，每项只算一次，算过的留给后面用。

dp 怎么定义，为什么非要三个种子

定义 dp[i] 就是第 i 个泰波那契数 T(i)，下标 i 对应第几项，格子里的值就是那一项的大小。起手必须铺满三个种子：dp[0]=0、dp[1]=1、dp[2]=1。

道理在转移式（从前面几格推出这一格的那条公式）上：每项要前三项相加，想算出第一个「非种子」的 dp[3]，手里得先攥着 dp[0]、dp[1]、dp[2]。斐波那契依赖前两项、两个种子够用；泰波那契依赖前三项就得多备一个。只给两个种子是最典型的错法，循环从 dp[3] 起就少一个数，推不动。

为什么前三项直接相加就是对的

转移式 dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 成立，是因为泰波那契的定义本身就这么规定——它不像求最值的题要在几条来路里挑最好的，而是把前三项原样加起来。

前三项一加，第 i 项的值就被唯一定死、没有第二种可能：只要 dp[i-1]、dp[i-2]、dp[i-3] 算对，dp[i] 就一定对。从左往右填，用到的三个数都是前面填好的，链条不会断。

拿 n=10 亲手加一遍

三个种子先摆好：dp[0]=0、dp[1]=1、dp[2]=1。从 dp[3] 开始，每格都是前三格之和：

dp[3] = dp[2]+dp[1]+dp[0] = 1+1+0 = 2 dp[4] = 2+1+1 = 4 dp[5] = 4+2+1 = 7 dp[6] = 7+4+2 = 13 dp[7] = 13+7+4 = 24 dp[8] = 24+13+7 = 44 dp[9] = 44+24+13 = 81 dp[10] = 81+44+24 = 149

填到 dp[10] 得到 149，和题目答案对上，这一列填出来的数就是泰波那契的前十一项。

复杂度多少，三个种子和溢出别弄错

从 dp[3] 推到 dp[n]，一共 n-2 格，每格一次加法，时间 O(n)；每项只用最近三项，不必存整表，用三个变量轮转——算完一格丢掉最老的、接上新算的，空间从 O(n) 压到 O(1)。

容易踩坑的有三处：种子只铺两个，循环起不来；n≤2 没特判会取到还没准备好的项，得让 n=0 返回 0、n=1 和 n=2 返回 1；数值溢出，本题 n≤37、T(37) 还在 int 内，但项一大长得飞快，扩到更大 n 就该换更大整数类型。

Python

def tribonacci(n):
    if n == 0: return 0
    if n <= 2: return 1
    a, b, c = 0, 1, 1   # T(i-3), T(i-2), T(i-1)
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c
    return c

C++

int tribonacci(int n){
    if(n == 0) return 0;
    if(n <= 2) return 1;
    long a = 0, b = 1, c = 1;
    for(int i = 3; i <= n; ++i){
        long d = a + b + c;
        a = b; b = c; c = d;
    }
    return (int)c;
}

Java

class Solution {
    int tribonacci(int n){
        if (n == 0) return 0;
        if (n <= 2) return 1;
        long a = 0, b = 1, c = 1;
        for (int i = 3; i <= n; i++) {
            long d = a + b + c;
            a = b; b = c; c = d;
        }
        return (int) c;
    }
}