LCR-126 斐波那契数

好的，下面是对 Java 实现斐波那契数列计算的详细解释，包括每个步骤的具体说明。

斐波那契数列计算

问题描述

斐波那契数列的定义如下：

• ( F(0) = 0 )
• ( F(1) = 1 )
• 对于 ( n > 1 )， ( F(n) = F(n-1) + F(n-2) )

本题的目标是计算给定 ( n ) 的斐波那契数，并将结果对 ( 10^9 + 7 ) 取模。

示例

• 输入：n = 2
  • 计算：F(2) = F(1) + F(0) = 1 + 0 = 1
  • 输出：1
• 输入：n = 3
  • 计算：F(3) = F(2) + F(1) = 1 + 1 = 2
  • 输出：2
• 输入：n = 4
  • 计算：F(4) = F(3) + F(2) = 2 + 1 = 3
  • 输出：3

Java 实现

以下是详细的代码实现和解释：

public class Fibonacci {

    // 方法用于计算斐波那契数
    public static int fib(int n) {
        // 定义常量 MOD 为 1000000007，用于取模运算
        final int MOD = 1000000007;

        // 基本情况：如果 n 是 0 或 1，直接返回 n
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        // 创建一个数组 dp 用于存储斐波那契数
        int[] dp = new int[n + 1];
        dp[0] = 0; // F(0) = 0
        dp[1] = 1; // F(1) = 1

        // 通过迭代计算斐波那契数，从 2 到 n
        for (int i = 2; i <= n; i++) {
            // F(i) = F(i-1) + F(i-2)，并对结果取模 MOD
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        // 返回计算得到的 F(n)
        return dp[n];
    }

    public static void main(String[] args) {
        // 示例测试
        int n = 2;
        System.out.println("F(" + n + ") = " + fib(n)); // 输出: 1

        n = 3;
        System.out.println("F(" + n + ") = " + fib(n)); // 输出: 2

        n = 4;
        System.out.println("F(" + n + ") = " + fib(n)); // 输出: 3
    }
}

代码详细解释

1. 常量定义:

   final int MOD = 1000000007;
   

   定义了一个常量 MOD 为 (10^9 + 7)，用于取模运算以防止结果溢出。

2. 基本情况处理:

   if (n == 0) {
       return 0;
   }
   if (n == 1) {
       return 1;
   }
   

   如果 n 为 0 或 1，直接返回相应的斐波那契数 F(0) = 0 或 F(1) = 1。

3. 数组初始化:

   int[] dp = new int[n + 1];
   dp[0] = 0; // F(0) = 0
   dp[1] = 1; // F(1) = 1
   

   创建一个长度为 n + 1 的数组 dp 用于存储斐波那契数，初始化 dp[0] 和 dp[1] 为 0 和 1。

4. 迭代计算:

   for (int i = 2; i <= n; i++) {
       dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
   }
   

   从 2 开始迭代到 n，通过状态转移方程 F(i) = F(i-1) + F(i-2) 计算斐波那契数，并对每次结果取模 MOD。

5. 返回结果:

   return dp[n];
   

   最后返回数组 dp 中的第 n 个元素，即所求的斐波那契数 F(n)。

6. 测试示例:

   public static void main(String[] args) {
       int n = 2;
       System.out.println("F(" + n + ") = " + fib(n)); // 输出: 1
   
       n = 3;
       System.out.println("F(" + n + ") = " + fib(n)); // 输出: 2
   
       n = 4;
       System.out.println("F(" + n + ") = " + fib(n)); // 输出: 3
   }