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);
        }
    }
}
相关文章
|
12月前
|
运维 安全 Linux
Linux中传输文件文件夹的10个scp命令
【10月更文挑战第18天】本文详细介绍了10种利用scp命令在Linux系统中进行文件传输的方法,涵盖基础文件传输、使用密钥认证、复制整个目录、从远程主机复制文件、同时传输多个文件和目录、保持文件权限、跨多台远程主机传输、指定端口及显示传输进度等场景,旨在帮助用户在不同情况下高效安全地完成文件传输任务。
1215 5
|
12月前
|
缓存 网络协议 JavaScript
【HTTP】构造HTTP请求和状态码
【HTTP】构造HTTP请求和状态码
190 1
【HTTP】构造HTTP请求和状态码
|
SQL 存储 监控
Linux查看Hive进程
【8月更文挑战第17天】
285 1
|
12月前
|
数据采集 前端开发 算法
Python Requests 的高级使用技巧:应对复杂 HTTP 请求场景
本文介绍了如何使用 Python 的 `requests` 库应对复杂的 HTTP 请求场景,包括 Spider Trap(蜘蛛陷阱)、SESSION 访问限制和请求频率限制。通过代理、CSS 类链接数控制、多账号切换和限流算法等技术手段,提高爬虫的稳定性和效率,增强在反爬虫环境中的生存能力。文中提供了详细的代码示例,帮助读者掌握这些高级用法。
638 1
Python Requests 的高级使用技巧:应对复杂 HTTP 请求场景
|
11月前
|
安全 API 数据安全/隐私保护
常见的HTTP请求方法
【10月更文挑战第25天】这些HTTP请求方法共同构成了客户端与服务器之间交互的基础,使得客户端能够根据不同的需求对服务器资源进行各种操作。在实际应用中,开发者需要根据具体的业务场景和资源的性质选择合适的请求方法来实现客户端与服务器之间的有效通信。
|
SQL 运维 监控
如何做数据库自动化运维
【5月更文挑战第5天】IT运维中的DBA面临诸多挑战,包括库表设计规范落地困难、SQL审核繁琐、数据提取需求频繁、资源管理和监控复杂。为解决这些问题,引入数据库自动化运维平台至关重要。该平台实现SQL审核自动化,确保语句规范和安全,支持数据提取的自助服务,强化元数据管理,提供一键资源部署,并进行全面的数据库监控。这样,DBA的角色转变为平台管理者,提高效率,规范化流程,减轻工作负担。
|
11月前
|
缓存 前端开发 API
|
缓存 NoSQL 应用服务中间件
Redis实战篇
Redis实战篇
|
缓存 NoSQL 关系型数据库
|
12月前
|
NoSQL 数据可视化 Linux
redis学习四、可视化操作工具链接 centos redis,付费Redis Desktop Manager和免费Another Redis DeskTop Manager下载、安装
本文介绍了Redis的两个可视化管理工具:付费的Redis Desktop Manager和免费的Another Redis DeskTop Manager,包括它们的下载、安装和使用方法,以及在使用Another Redis DeskTop Manager连接Redis时可能遇到的问题和解决方案。
1359 1
redis学习四、可视化操作工具链接 centos redis,付费Redis Desktop Manager和免费Another Redis DeskTop Manager下载、安装