GESP 六级 · GESP 202509 C++ 六级 第 24 题

下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度为 $O(2^n)$。

int fib_dp(int n) {
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

斐波那契数列：f(1)=f(2)=1，f(n)=f(n-1)+f(n-2)。递归实现简单但效率低（O(2^n)），循环实现O(n)。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】动态规划 (DP)｜时间复杂度分析

命题人把"动态规划"和"O(2^n)"强行绑定，卡住的是对DP本质理解不足的考生——以为只要用DP就必然指数级，忽略了DP的核心价值是消除重复子问题。

代码里只有一层循环，每次迭代 O(1)，总时间 O(n)。命题人想考察你能否一眼看出循环次数即复杂度，而不是死记结论。

错误选项 A 利用"动态规划=指数复杂度"的刻板印象，把递归版斐波那契的 O(2^n) 偷换到 DP 版本上。如果你只背结论、不理解本质，就会掉进这个陷阱。

如果把题目改成"不使用数组而用递归"或"循环内嵌套循环"，复杂度都会变：递归版 O(2^n)，双层循环 O(n²)。刷到类似题先问：命题人想考我什么？

DP 的递推式本身是 O(1) 计算，数组只存中间结果，不改变阶。空间是 O(n)，但时间复杂度看循环次数。典型 DP 都是 O(1) 转移。