题解 | #牛牛学数列5#

题目链接

牛牛学数列5

题目描述

斐波那契数列定义如下：

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2) (for n > 2)

给定一个整数 n，计算并输出斐波那契数列的第 n 项 F(n) 的值。

输入描述: 输入一个整数 n (1 ≤ n ≤ 40)。

输出描述: 输出一个整数，表示 F(n) 的值。

解题思路

本题要求计算斐波那契数列的第 n 项。这是一个非常经典的算法问题，有多种解法，但考虑到 n 的范围（最大为40），最适合的是迭代法（也称为自底向上的动态规划）。

递归法 (Inefficient)

最直接的想法是把数学公式 F(n) = F(n-1) + F(n-2) 直接翻译成递归函数。

function fib(n):
  if n <= 2: return 1
  return fib(n-1) + fib(n-2)

这种方法虽然直观，但效率极低。例如，在计算 fib(5) 时，会分别计算 fib(4) 和 fib(3)。而 fib(4) 又会去计算 fib(3) 和 fib(2)。可以看到，fib(3) 被重复计算了。随着 n 的增大，这种重复计算会呈指数级增长，导致严重超时。对于 n=40，纯递归是不可行的。

迭代法 / 动态规划 (Efficient O(n) Solution)

为了避免递归中大量的重复计算，我们可以采用自底向上的方式，从斐波那契数列的最小项开始，一步步计算并存储结果，直到我们得到第 n 项。这正是动态规划的核心思想。

思路：使用数组存储结果 (DP Table) 这是最标准的动态规划解法。我们创建一个数组（比如 dp），dp[i] 用来存储斐波那契数列的第 i 项 F(i) 的值。

算法步骤:

处理边界情况: 如果 n 小于等于 2，结果直接是 1。
创建数组: 创建一个大小为 n+1 的数组 dp 来存储结果。
定义初始值: 根据斐波那契数列的定义，设置 dp[1] = 1 和 dp[2] = 1。
递推计算: 从 i = 3 循环到 n，根据递推公式 F(n) = F(n-1) + F(n-2) 来填充数组。在我们的数组中，这就表现为 dp[i] = dp[i-1] + dp[i-2]。
获取结果: 循环结束后，数组的最后一项 dp[n] 就是我们要求的 F(n)。

这种方法思路非常清晰，将数学定义直接转化为了代码实现。对于 n=40 的范围来说，这是一个非常高效和标准的解法。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    if (n <= 2) {
        cout << 1 << endl;
        return 0;
    }
    
    // 创建一个大小为 n+1 的数组来存储斐波那契数
    // dp[i] 将存储 F(i)
    vector<int> dp(n + 1);
    
    // 设置初始值
    dp[1] = 1;
    dp[2] = 1;
    
    // 从3到n进行递推
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n <= 2) {
            System.out.println(1);
            return;
        }

        // 创建一个大小为 n+1 的数组
        int[] dp = new int[n + 1];

        // 设置初始值
        dp[1] = 1;
        dp[2] = 1;

        // 从3到n进行递推
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        System.out.println(dp[n]);
    }
}

n = int(input())

if n <= 2:
    print(1)
else:
    # 创建一个大小为 n+1 的列表，用0填充
    dp = [0] * (n + 1)
    
    # 设置初始值
    dp[1] = 1
    dp[2] = 1
    
    # 从3到n进行递推
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    print(dp[n])

空间优化

我们观察到，在计算 dp[i] 时，我们实际上只用到了它前面的两项：dp[i-1] 和 dp[i-2]。更早的项（如 dp[i-3] 等）就再也用不到了。因此，我们没有必要存储整个数组，可以只用两个变量来滚动记录前两项的值，从而将空间复杂度从 O(n) 优化到 O(1)。

算法及复杂度

算法：动态规划 (使用数组)。
时间复杂度： $\mathcal{O}(n)$ ，因为我们执行一个从 3 到 n 的线性循环来填充数组。
空间复杂度： $\mathcal{O}(n)$ ，因为我们使用了一个大小与 n 成正比的数组来存储中间结果。 (注：此空间可以被优化到 $\mathcal{O}(1)$ )。