01_斐波那契数列

简介: 01_斐波那契数列

509. 斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你n ,请计算 F(n) 。

示例 1:

  • 输入:2
  • 输出:1
  • 解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

  • 输入:3
  • 输出:2
  • 解释:F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3:

  • 输入:4
  • 输出:3
  • 解释:F(4) = F(3) + F(2) = 2 + 1 = 3

提示:

  • 0 <= n <= 30

【思路】

练练手为主,就像之前讲过二叉树系列的递归三部曲 (opens new window),回溯法系列的回溯三部曲 (opens new window)一样。后面慢慢大家就会体会到,动规五部曲方法的重要性。

动态规划五部曲

动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果

1、确定dp数组及其下标的含义

dp[i]的定义为:第i个数的斐波那契数值为dp[i]

2、确定递推公式

dp[i]=dp[i-1]+dp[i-2]

3、dp数组如何初始化

dp[0]=1;
dp[1]=1;

4、确定遍历顺序

从递推公式dp[i] = dp[i-1] + dp[i-2];可以看出,dp[i]是依赖于dp[i-1]和dp[i-2]的,那么遍历的顺序一定是从前往后来遍历的

5、举例推到di数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来,发现结果不对,就把dp数组打印出来看看和我们推导的数列是不是一致的。

以上我们用动规的方法分析完了,java代码如下:

//非压缩版本的写法
class Solution {
  public int fib(int N) {
    if (N <= 1) 
      return N;
    int[] dp = new int[N+1];
        dp[0] = 1;
        dp[1] = 1;
    for (int i = 2; i <= N; i++) {
      dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[N];
  }
}
//压缩版本的写法
public int fib(int n) {
    if (n <= 1) {
        return n;
    }
  int a = 0, b = 1, c = 0;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
JAVA 复制 全屏

方法二、传统的递归法

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }
}
相关文章
|
存储 边缘计算 运维
核心网架构 | 带你读《5G时代的承载网》之十三
对 5G 核心网进行了颠覆性的设计,通过基于服务的架构、网络切片、C/U 分离等,结合云化技术,实现网络的定制化、开放化、服务化,支持大流量、 大连接和低时延的万物互联需求。
核心网架构  | 带你读《5G时代的承载网》之十三
|
IDE Java 开发工具
java编译通过,运行却提示找不到或无法加载主类的解决方案
java编译通过,运行却提示找不到或无法加载主类的解决方案
3068 0
|
监控 自动驾驶 数据可视化
GPS 人员定位系统:原理拆解 + 优劣分析 + 避坑指南(一)
本文详解GPS人员定位系统的工作原理,从卫星测距、三角定位到数据解算,解析其实现过程,并介绍实时定位、电子点名、轨迹回溯、智能考勤等核心功能,为后续优劣分析与避坑指南做铺垫。
|
2月前
|
人工智能 自然语言处理 运维
医疗设备售后智能客服部署模式对比:SaaS还是私有化,医院和器械AI客服怎么选
医疗设备售后 AI 客服选 SaaS 还是私有化,核心取决于数据敏感度、业务系统连接深度、AI 执行权限和企业 IT 运维能力。只承担知识问答和基础咨询的 AI 客服可优先考虑 SaaS;涉及核心业务系统和深度售后流程时,应进一步评估私有化或混合部署。
341 7
|
2月前
|
存储 OLAP OLTP
从OLTP到OLAP到HTAP:数据库负载分类的技术演进与选型指南
OLTP和OLAP是数据库最常被混淆的一对概念。很多人知道“OLTP是交易,OLAP是分析”,但不清楚它们在存储结构、索引设计、执行引擎上的根本差异。本文从数据组织方式、查询模式、优化目标三个层面,拆解OLTP和OLAP的本质区别,并结合实际使用场景给出选型建议。
|
9月前
|
人工智能 运维 安全
AI编程辅助实操踩坑记:注意事项与高效使用技巧
重复编码的内耗、紧急需求的赶工压力、小众场景的调试困境,或许是每一位开发者日常工作中都绕不开的难题。当各类AI编程工具扎堆出现,要么侧重单一补全功能、要么部署门槛过高,开源AI研发基础设施类编程辅助利器,以“轻量化部署+全链路赋能”的差异化优势,悄然成为我化解编码痛点的搭档,但是...
|
存储 安全 算法
鸿蒙NEXT如何保证应用安全:详解鸿蒙NEXT数字签名和证书机制
本文对鸿蒙NEXT公开资料进行了深入分析和解读,梳理了鸿蒙单框架应用的签名机制,拆解每一步的实操过程和背后的实现原理,并对源码分析整理签名的校验机制。从中管中窥豹,探究鸿蒙系统的安全设计思路,给从事鸿蒙研发的同学提供一些借鉴。
1942 3
|
数据采集 缓存 安全
2024年最佳http 代理 IP选择及其价格分析
2024年,多家服务商如快代理、123Proxy、巨量代理、IPIDEA等提供不同类型的代理IP,以满足数据采集、跨境电商等多种需求。
1232 5
2024年最佳http 代理 IP选择及其价格分析
|
运维 网络安全 网络虚拟化
2024网络建设与运维赛题-网络配置VRF教程-上
本文讲解了采用神州数码的CS6200-28X-Pro三层交换机配置涉及VRF分支和互联网接口,每个核心交换机(SW1-SW3)的Loopback接口和VLAN接口分配了特定的IP地址,用于VRF分支和Internet连接。配置示例展示了SW1到SW3的VRF与IP地址设置,用于实现网络隔离和互联互通。
2024网络建设与运维赛题-网络配置VRF教程-上
|
XML Java API
Android翻转动画(卡片翻转效果)
本文介绍了如何实现卡片翻转动画效果,通过Android中的ObjectAnimator结合不同插值器(LinearInterpolator、AccelerateInterpolator、DecelerateInterpolator)完成平滑过渡。示例中以按钮点击触发动画,核心逻辑包括判断视图可见性、设置旋转角度及处理初始Bug(如第一次点击异常)。最终提供完整代码(Java与XML布局),并指出将按钮事件替换为屏幕监听即可满足右滑触发需求。适合初学者学习动画实现原理。
619 0