蓝桥试题：斐波那契数列

一、题目要求

斐波那契数列定义为  f(n) = f(n - 1) + f(n - 2)，同时f(1) = 1 , f(2) = 1

请输出数列的第n个数对 1e9 + 7 取模的值

二、代码展示 import java.util.Arrays; import java.util.Scanner; public class ikun { static long []dp; static long mod = (long) 1e9 + 7; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); dp = new long[n + 1]; Arrays.fill(dp , -1); dp[1] = 1; dp[2] = 1; System.out.println(dfs(n)); } public static long dfs(int n){ if (dp[n] != -1){ //对应 f(1) 和 f(2) return dp[n]; } long ans = dfs(n - 1) + dfs(n - 2); ans %= mod; dp[n] = ans; return dp[n]; } }

该Java程序用于计算斐波那契数列的第n项，并对结果取模 1e9+7。以下是代码的详细解释：

代码结构

类与变量：

dp 数组：动态规划缓存，存储已计算的斐波那契数值。

mod：模数 1e9 + 7，防止数值溢出。

主方法 main：

读取用户输入的整数 n。

初始化 dp 数组大小为 n+1，填充为 -1（表示未计算）。

设置初始条件 dp[1] = 1 和 dp[2] = 1，对应斐波那契数列的前两项。

调用递归方法 dfs(n) 并输出结果。

递归方法 dfs：

基础情况：若 dp[n] 已计算（不为 -1），直接返回缓存值。

递归计算：通过 dfs(n-1) + dfs(n-2) 计算第n项，并对结果取模。

缓存结果：将计算结果存入 dp 数组，避免重复计算。

斐波那契数列定义

初始条件：𝐹(1)=1   𝐹(2)=1

递推关系：𝐹(𝑛)=𝐹(𝑛−1)+𝐹(𝑛−2)mod  (1e9 + 7)

时间复杂度与优化

时间复杂度：𝑂(𝑛)O(n)，每个数仅计算一次。

空间复杂度：𝑂(𝑛)O(n)，用于存储 dp 数组。

总结

该程序通过记忆化搜索高效计算斐波那契数列的第n项，适用于中等规模的输入。初始条件设定和递推关系符合标准斐波那契数列定义，结果经取模确保数值范围合理。