1. 问题背景与递归的局限性
斐波那契数列的定义是：
F(n)=F(n−1)+F(n−2)
其中，F(0)=0，F(1)=1。
对于求解斐波那契数列的第 n 项，我们最直接的方式是用递归来表达：
public static int fibonacciRecursive(int n) {if (n == 0) return 0;if (n == 1) return 1;return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
虽然递归看起来简单优雅，但这种方式的效率非常低。每次计算时，会重复地计算同样的子问题。比如在计算 F(5) 时，会多次计算 F(3) 和 F(2)。这导致了时间复杂度为 O(2^n)，增长极快，适用于较小的 n 值，但当 n 较大时，计算变得非常慢。
2. 动态规划的思想
动态规划的核心思想是避免重复计算，通过记忆化（Memoization）或自底向上（Bottom-Up）的方式来解决问题。斐波那契数列的问题可以被分解为很多子问题，而这些子问题之间有重叠。动态规划通过保存子问题的解，避免了重复计算。
动态规划的两个特点：
- 重叠子问题：大问题可以分解成若干小问题，而小问题的解会被多次使用。
- 最优子结构：一个问题的最优解可以由其子问题的最优解构成。
斐波那契数列具备这两个特性，因此可以通过动态规划来高效求解。
3. Java代码实现动态规划求解斐波那契数列
我们来看使用动态规划的实现：
public class FibonacciDP {public static void main(String[] args) {int n = 10; // 求第n个斐波那契数System.out.println("Fibonacci number at position " + n + " is: " + fibonacci(n));}public static int fibonacci(int n) {// 边界条件处理if (n == 0) {return 0; // F(0) = 0}if (n == 1) {return 1; // F(1) = 1}// 动态规划数组，用于存储中间结果int[] dp = new int[n + 1];dp[0] = 0; // F(0)dp[1] = 1; // F(1)// 自底向上计算斐波那契数列的值for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]; // 当前项由前两项之和得出}return dp[n]; // 返回第n个斐波那契数}
}
4. 详细解释每个部分
4.1 边界情况处理
斐波那契数列有两个特殊情况：
- 当
n = 0时，返回0。 - 当
n = 1时，返回1。
这两个条件在代码中通过以下部分处理：
if (n == 0) {return 0;
}
if (n == 1) {return 1;
}
这确保了程序能够正确处理最小的输入值。
4.2 动态规划数组
为了避免递归中的重复计算，我们引入一个数组 dp[] 来保存每一步计算的结果。数组的大小为 n+1，即它包含了从 F(0) 到 F(n) 的所有结果。初始化数组中的前两个值：
int[] dp = new int[n + 1];
dp[0] = 0; // F(0)
dp[1] = 1; // F(1)
这里的 dp[0] 和 dp[1] 对应斐波那契数列的前两项。
4.3 填充动态规划数组
接下来，通过一个 for 循环，从第3项（i=2）开始，依次计算每一个斐波那契数，并将结果存储到数组中。
for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]; // 递推公式 F(i) = F(i-1) + F(i-2)
}
这个循环的逻辑很简单：根据斐波那契数列的定义，第 i 项等于前两项之和，因此 dp[i] = dp[i - 1] + dp[i - 2]。
4.4 返回结果
当循环结束后，数组 dp[n] 已经存储了第 n 个斐波那契数的值，我们只需将其返回：
return dp[n];
5. 时间复杂度与空间复杂度
时间复杂度： 整个过程我们只遍历了一次 dp[] 数组，从 i=2 到 i=n，因此时间复杂度为 O(n)，相比递归的 O(2^n)，大大提升了效率。
空间复杂度： 由于我们使用了一个长度为 n+1 的数组，因此空间复杂度为 O(n)。
6. 空间优化
虽然上面的解法已经非常高效，但还可以进一步优化空间复杂度。实际上，我们每次只需要用到前两项的值，因此可以不用数组，而是使用两个变量来代替 dp[] 数组。优化后的代码如下：
public static int fibonacciOptimized(int n) {if (n == 0) return 0;if (n == 1) return 1;int prev2 = 0; // F(0)int prev1 = 1; // F(1)int current = 0;for (int i = 2; i <= n; i++) {current = prev1 + prev2; // F(i) = F(i-1) + F(i-2)prev2 = prev1; // 更新 F(i-2)prev1 = current; // 更新 F(i-1)}return current; // 返回第n个斐波那契数
}
在这个版本中，我们只使用了三个变量来保存前两项的值以及当前项，从而将空间复杂度优化到了 O(1)。
总结
- 动态规划的关键是避免重复计算，通过保存子问题的结果提升效率。
- 斐波那契数列的求解可以从递归优化为动态规划，从而将时间复杂度从
O(2^n)降到O(n)。 - 可以进一步优化空间复杂度，将
O(n)降到O(1)，使用两个变量代替数组存储中间结果。