斐波那契数列是动态规划中一个经典的模型，其递推关系简单易懂，非常适合作为入门练习。斐波那契数列的定义如下：
在 Java 中，可以通过递归、带记忆化的递归、迭代和优化空间复杂度的方式实现斐波那契数列。
1. 递归实现
最直观的实现，但存在大量重复计算，时间复杂度为 O(2n)。
public class Fibonacci {
public static int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println(fib(10)); // 输出：55
}
}
2. 带记忆化的递归
通过一个数组存储已计算的值，避免重复计算，时间复杂度降为 O(n)。
import java.util.Arrays;
public class Fibonacci {
public static int fib(int n, int[] memo) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != -1) return memo[n]; // 如果已经计算过，直接返回
memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // 递归计算并存储结果
return memo[n];
}
public static void main(String[] args) {
int n = 10;
int[] memo = new int[n + 1];
Arrays.fill(memo, -1); // 初始化为-1，表示未计算
System.out.println(fib(n, memo)); // 输出：55
}
}
3. 迭代实现
通过循环代替递归，更高效且无栈溢出风险。
public class Fibonacci {
public static int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int prev1 = 0, prev2 = 1;
int current = 0;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return current;
}
public static void main(String[] args) {
System.out.println(fib(10)); // 输出：55
}
}
4. 优化空间复杂度
实际上，只需要存储前两个状态，进一步减少空间复杂度为 O(1)。
public class Fibonacci {
public static int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
public static void main(String[] args) {
System.out.println(fib(10)); // 输出：55
}
}
动态规划的特点
- 最优子结构：当前问题的解可以通过子问题的解推导得到。
- 重叠子问题：通过存储子问题的解，避免重复计算。
- 状态转移方程：明确从子问题到当前问题的递推关系。
在斐波那契数列中：
- 状态定义：dp[i] 表示第 i 个斐波那契数。
- 状态转移方程：dp[i]=dp[i−1]+dp[i−2]。
这些实现方式可以根据实际场景选择合适的方式，例如对于较大规模的 n，推荐使用迭代或优化空间复杂度的解法。
发布者：myrgd，转载请注明出处：https://www.object-c.cn/4344
