斐波那契数列是我们在编程中经常会遇到的一个经典问题。它的定义很简单：第0项是0，第1项是1，从第2项开始，每一项都等于前两项之和。用数学公式表示就是：f(0) = 0，f(1) = 1，当n > 1时，f(n) = f(n-1) + f(n-2)。
如果我们想计算f(5)，可以一步步算：f(2)=f(1)+f(0)=1+0=1，f(3)=f(2)+f(1)=1+1=2，f(4)=f(3)+f(2)=2+1=3，f(5)=f(4)+f(3)=3+2=5。这个过程看起来很简单，但如果n变得很大，比如n=100，直接用这种方法计算会怎么样呢？
暴力递归法的问题¶
我们先尝试用最简单的递归方法来写代码：
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
这个方法的问题在于重复计算太多。比如计算f(5)时，fib(3)被计算了两次，fib(2)被计算了三次；计算f(10)时，fib(5)会被计算多次。随着n增大，重复计算的次数呈指数级增长，时间复杂度高达O(2^n)，几乎不可用。
动态规划的核心思想¶
动态规划的核心是“记住已经解决过的子问题答案，避免重复计算”。就像我们做数学题时，如果遇到“已经算过的步骤”，就直接用结果，不用再从头算一遍。
1. 记忆化递归（带备忘录）¶
我们可以用一个数组（备忘录）来存储已经计算过的斐波那契数。当需要计算f(n)时，先检查备忘录中是否已有结果，如果有就直接返回；如果没有，计算后再存入备忘录。
代码实现：
int fib(int n) {
if (n <= 1) return n;
vector<int> memo(n + 1, -1); // 备忘录数组，初始化为-1表示未计算
return helper(n, memo);
}
int helper(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // 已计算过，直接返回
memo[n] = helper(n - 1, memo) + helper(n - 2, memo); // 计算并存储结果
return memo[n];
}
这个方法中，每个f(k)只计算一次，时间复杂度是O(n)，空间复杂度是O(n)（备忘录数组）。
2. 递推法（从底向上迭代）¶
更高效的方法是迭代。因为斐波那契数列的每一项只依赖前两项，我们可以用两个变量记录前两项的值，依次迭代计算下一项，无需额外数组空间。
代码实现：
int fib(int n) {
if (n <= 1) return n;
int a = 0; // f(0)
int b = 1; // f(1)
for (int i = 2; i <= n; ++i) {
int c = a + b; // 计算当前项
a = b; // 更新前一项
b = c; // 更新当前项
}
return b;
}
这个方法的时间复杂度是O(n)，空间复杂度是O(1)，是最优解法。
动态规划的关键特性¶
通过斐波那契数列，我们能理解动态规划的两个核心特性：
1. 重叠子问题：大问题分解为小问题，且小问题会被重复计算（如f(3)在计算f(5)和f(4)时都需要）。
2. 最优子结构：当前问题的解依赖于子问题的解（f(n) = f(n-1) + f(n-2)）。
总结¶
动态规划的本质是用空间换时间，通过存储子问题的结果避免重复计算。斐波那契数列是动态规划的经典入门案例，从暴力递归到记忆化递归再到递推法，每一步都体现了优化的思路。掌握这个方法后，我们可以解决更复杂的问题，如爬楼梯、最长公共子序列等。
从现在开始，尝试用动态规划思想解决更多实际问题吧！