当前位置：首页 > article >正文

动态规划算法之斐波那契数列详细解读（附带Java代码解读）

article 2024/11/20 19:23:22

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)。