斐波那契数 图解题解

斐波那契数这道题到底在算什么

给一个整数 n，返回斐波那契数列的第 n 项 F(n)。规矩很简单：F(0)=0、F(1)=1，从第 2 项起每项等于前两项之和 F(n)=F(n-1)+F(n-2)。题目例子 n=10 答案 55，数列从头是 0、1、1、2、3、5、8、13、21、34、55。难在怎么算——同一个数列，写法不同能差出天上地下。

为什么照定义裸递归会慢到跑不动

最顺手的写法是照定义递归：fib(n) 返回 fib(n-1)+fib(n-2)，n<2 返回 n。但它把同一个子问题反复重算。算 fib(5) 要 fib(4) 和 fib(3)，fib(4) 又要 fib(3) 和 fib(2)——fib(3) 被算两遍。整棵调用树里，算一个 fib(5) 发生 15 次调用，fib(2) 重算 3 次、fib(1) 重算 5 次，结果却只是 5。

n 一大重复就滚成指数，时间复杂度 O(2^n)（大 O 记号描述规模变大时操作数怎么涨），算到 fib(50) 已是几十亿次调用。慢的根子是每个子问题都从零重算。

改成自底向上，dp[i] 存的就是 F(i)

既然子问题被重复算，就让每个只算一次、把结果存下来。定义 dp[i] 表示第 i 项 F(i)，下标 i 就是项号。开头两格按定义填死 dp[0]=0、dp[1]=1，它们是种子，不套转移式（转移式就是由前几项推出当前项的式子，这里前面没有两格可加）。从第 2 项起每格照 dp[i]=dp[i-1]+dp[i-2] 往右推，用的都是已算好的前两格。

这就是自底向上：从最小子问题往大推，推到 dp[n] 就是答案。记忆化递归（自顶向下，算过的存表直接取）效果一样，都把 O(2^n) 压回 O(n)。

为什么整张表可以只留两个变量

算第 i 格只用得上紧挨的前两格。既然只需前两项，就没必要开整个数组，用两个变量轮着装即可——这叫滚动变量（只留最近几项、循环覆盖旧值）。

参考代码里 a、b 起初是 0 和 1，每轮做 a, b = b, a + b，相当于把窗口向右挪一格。循环跑完 b 就是 F(n)，空间从 O(n) 降到 O(1)。

拿 n=10 亲手把整串数推一遍

两个种子先摆好 dp[0]=0、dp[1]=1。从第 2 项起每格是前两格相加：dp[2]=1+0=1；dp[3]=1+1=2；dp[4]=2+1=3；dp[5]=3+2=5；dp[6]=5+3=8；dp[7]=8+5=13；dp[8]=13+8=21；dp[9]=21+13=34；dp[10]=34+21=55。

推到 dp[10] 得 55，和题目答案对上；用滚动变量做，最后 b 也是 55。

复杂度是多少，n=0/1 的边界怎么收

从第 2 项推到第 n 项是一趟线性循环，每格一次加法，共 O(n) 次操作；只用 a、b 两个变量，空间 O(1)。

两个边界最容易踩坑。一是 n<2：n=0 返回 0、n=1 返回 1，直接返回 n，别硬套转移式访问不存在的前两格。二是起点别写反，dp[0]=0、dp[1]=1 反了整列会全错，照定义抄时最常见。

Python

def fib(n):
    if n < 2:
        return n
    a, b = 0, 1   # dp[i-2], dp[i-1]
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

C++

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

Java

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