剑指 Offer:10- I. 斐波那契数列

简介: 剑指 Offer:10- I. 斐波那契数列

1. 题目

剑指 Offer 10- I. 斐波那契数列


2. 描述

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:


F(0) = 0, F(1) = 1


F(N) = F(N - 1) + F(N - 2), 其中 N > 1.


斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。


答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。


示例 1:


输入:n = 2


输出:1


示例 2:


输入:n = 5


输出:5


提示:


0 <= n <= 100


3. 实现方法

3.1 方法 1

3.1.1 思路

F(0) = 0, F(1) = 1


F(N) = F(N - 1) + F(N - 2), 其中 N > 1


利用递归的方法, 把 f ( n ) f(n)f(n) 问题的计算拆分成 f ( n − 1 ) f(n−1)f(n−1) 和 f ( n − 2 ) f(n−2)f(n−2) 两个子问题的计算,并递归,以 f ( 0 ) f(0)f(0) 和 f ( 1 ) f(1)f(1) 为终止条件,虽然能求出结果,但是最终会超时;


3.1.2 实现


class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n % 1000000007;
        }
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}

3.2 方法 2

3.2.1 思路

F(0) = 0, F(1) = 1


F(N) = F(N - 1) + F(N - 2), 其中 N > 1


利用上述条件,利用动态规划的思想;


状态定义: 设 d p dpdp 为一维数组,其中 d p [ i ] dp[i]dp[i] 的值代表 斐波那契数列第 i ii 个数字 。

转移方程: d p [ i + 1 ] = d p [ i ] + d p [ i − 1 ] dp[i + 1] = dp[i] + dp[i - 1]dp[i+1]=dp[i]+dp[i−1],即对应数列定义 $f(n + 1) = f(n) + f(n - 1) $;

初始状态: d p [ 0 ] = 0 dp[0] = 0dp[0]=0, d p [ 1 ] = 1 dp[1]=1dp[1]=1 ,即初始化前两个数字;

返回值: d p [ n ] dp[n]dp[n] ,即斐波那契数列的第 n nn 个数字

时间复杂度:此时主要进行循环操作,时间复杂度为 O ( n ) O(n)O(n);

3.2.2 实现


public int fib(int n) {
    int first = 0;
    int second = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = (first + second) % 1000000007;
        first = second;
        second = sum;
    }
    return first;
}
目录
相关文章
|
10天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1208 5
|
9天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1171 87
|
8天前
|
机器学习/深度学习 物联网
Wan2.2再次开源数字人:Animate-14B!一键实现电影角色替换和动作驱动
今天,通义万相的视频生成模型又又又开源了!Wan2.2系列模型家族新增数字人成员Wan2.2-Animate-14B。
653 11
|
9天前
|
云栖大会
阿里云云栖大会2025年9月24日开启,免费申请大会门票,速度领取~
2025云栖大会将于9月24-26日举行,官网免费预约畅享票,审核后短信通知,持证件入场
1762 12
|
19天前
|
人工智能 运维 安全
|
2天前
|
资源调度
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
除了nrm-pm,还有哪些工具可以管理多个包管理器的源?
229 127
|
10天前
|
弹性计算 Kubernetes jenkins
如何在 ECS/EKS 集群中有效使用 Jenkins
本文探讨了如何将 Jenkins 与 AWS ECS 和 EKS 集群集成,以构建高效、灵活且具备自动扩缩容能力的 CI/CD 流水线,提升软件交付效率并优化资源成本。
362 0

热门文章

最新文章