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

这篇具有很好参考价值的文章主要介绍了剑指 Offer 10- I. 斐波那契数列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

方法一

class Solution {
    int mod = (int) 1e9 + 7;
    
    public int fib(int n) {
        if(n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;

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

        return dp[n];
    }
}

方法二

对方法一进行空间优化。文章来源地址https://www.toymoban.com/news/detail-694981.html

class Solution {
    int mod = (int) 1e9 + 7;
    
    public int fib(int n) {
        if(n <= 1) return n;
        int a = 0, b = 1;

        for(int i = 2; i <= n; i++){
            int c = (a + b) % mod;
            a = b;
            b = c;
        }

        return b;
    }
}

到了这里,关于剑指 Offer 10- I. 斐波那契数列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法学习】斐波那契数列模型-动态规划

            我在算法学习过程中,针对斐波那契数列模型的动态规划的例题进行了一个整理,并且根据标准且可靠一点的动态规划解题思路进行求解类似的动归问题,来达到学习和今后复习的必要。         所谓的斐波那契数列模型,即当前状态的值等于前两种状态的值之和。

    2024年02月04日
    浏览(54)
  • 【算法】斐波那契数列通项公式

    如果数列 a n a_n a n ​ 的递推公式: a n = c 1 a n − 1 + c 2 a n − 2 a_n=c_1a_{n-1}+c_2a_{n-2} a n ​ = c 1 ​ a n − 1 ​ + c 2 ​ a n − 2 ​ ------(1) 根据待定系数法,假设 a n − x a n − 1 = y ( a n − 1 − x a n − 2 ) a_n-xa_{n-1}=y(a_{n-1}-xa_{n-2}) a n ​ − x a n − 1 ​ = y ( a n − 1 ​ − x a n − 2 ​

    2023年04月24日
    浏览(46)
  • 【算法优选】 动态规划之斐波那契数列模型

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契

    2024年02月05日
    浏览(56)
  • C语言经典算法实例6:斐波那契数列

    斐波那契数列指的是这样一个数列:1,1,2,3,5,8,13,21,34,55,89… 这个数列从第3项开始,每一项都等于前两项之和。 斐波那契数列的定义者,是意大利数学家莱昂纳多·斐波那契(Leonardo Fibonacci),生于公元1170年,卒于1250年,籍贯是比萨。 他被人称作“比萨的莱昂

    2024年02月02日
    浏览(44)
  • C++算法 —— 动态规划(1)斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月10日
    浏览(44)
  • 一分钟学算法-递归-斐波那契数列递归解法及优化

    一分钟学一个算法题目。 今天我们要学习的是用递归算法求解斐波那契数列。 视频教程链接:https://www.bilibili.com/video/BV1Wu4y1i7JJ/ 首先我们要知道什么是斐波那契数列。 斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都

    2024年02月11日
    浏览(50)
  • 递归以及斐波那契数列递归算法和迭代算法的实现与分析

    程序调用自身的编程技巧称为递归( recursion) 递归有两个过程,简单地说一个是 递的过程 ,一个是 归的过程 。 递归的两个必要条件 1. 存在限制条件 ,当满足这个限制条件的时候,递归便不再继续。 2.每次递归调用之后越来越 接近这个限制条件 . 递归本质就是函数调用

    2024年02月12日
    浏览(37)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)
  • 线性代数 --- 计算斐波那契数列第n项的快速算法(矩阵的n次幂)

    The n-th term of Fibonacci Numbers:         斐波那契数列的是一个古老而又经典的数学数列,距今已经有800多年了。关于斐波那契数列的计算方法不难,只是当我们希望快速求出其数列中的第100,乃至第1000项时,有没有又准又快的方法,一直是一个值得探讨和研究的问题。笔者

    2024年04月27日
    浏览(45)
  • JAVA-斐波那契数列

    输入一个整数 n ,求斐波那契数列的第 n 项。 假定从 0 开始,第 0 项为 0 。 数据范围 0≤n≤39 样例

    2024年02月10日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包