斐波那契数列
入门斐波那契是 DP 最简单的重叠子问题示例。
// 算法讲解
斐波那契数列
用 DP 逐步计算 F(n)，避免递归的重复计算。
待机
速度 中
待机 ⌨1long long fibonacci(int n) {
2 if (n <= 1) return n;
3 long long prev2 = 0, prev1 = 1;
4 for (int i = 2; i <= n; i++) {
5 long long cur = prev1 + prev2;
6 prev2 = prev1;
7 prev1 = cur;
8 }
9 return prev1;
10}
复杂度分析
时间 O(n)
空间 O(1)
最优 O(log n) 矩阵法
最坏 O(n)
算法讲解
斐波那契数列定义为 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。
朴素递归的时间复杂度为 O(2^n)，因为大量子问题被重复计算。
用 DP 记录已计算的值后，每个 F(i) 只算一次，时间降为 O(n)。
进一步可以用矩阵快速幂在 O(log n) 内求出 F(n)，这是 DP 优化思维的自然延伸。