首页 > 其他分享 >刷刷刷 Day 38 | 509. 斐波那契数

刷刷刷 Day 38 | 509. 斐波那契数

时间:2023-02-26 11:22:06浏览次数:53  
标签:契数 38 int 斐波 数组 509 dp

509. 斐波那契数

LeetCode题目要求

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

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

给定 n ,请计算 F(n) 。

示例

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

输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2
解题思路

要用一个一维 dp 数组来保存递归的结果
五部曲

  1. 确定dp数组以及下标的含义 dp[i]的定义为:第i个数的斐波那契数值是dp[i]
  2. 确定递推公式:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组如何初始化:dp[0] = 0; dp[1] = 1;
  4. 确定遍历顺序:dp[i] 依赖 dp[i - 1] 和 dp[i - 2],遍历顺序是从前到后遍历的
  5. 举例推导dp数组:当N为10的时候,dp数组应该是如下的数列:0 1 1 2 3 5 8 13 21 34 55

上代码

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }

        // 1 确定数组 dp
        int[] dp = new int[n+1];
        
        // 3 dp 初始化
        dp[0] = 0;
        dp[1] = 1;

        // 4 遍历顺序
        for (int i = 2; i <= n; i++) {
            // 2 递推公式
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
}

精简版

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 1; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}
重难点

理解五部曲

附:学习资料链接

标签:契数,38,int,斐波,数组,509,dp
From: https://www.cnblogs.com/blacksonny/p/17156336.html

相关文章

  • 刷刷刷 Day 37 | 738. 单调递增的数字
    738.单调递增的数字LeetCode题目要求当且仅当每个相邻位数上的数字 x 和 y 满足 x<=y 时,我们称这个整数是单调递增的。给定一个整数n,返回小于或等于n的最......
  • CF1383E 题解
    题意传送门给定一个长度为\(n\)的01串\(a\)。在一次操作中,你可以选择任意一个\(i\in[1,|a|)\),令\(a_i=\max(a_i,a_{i+1})\),然后将\(a_{i+1}\)删除。你可以进行......
  • LQB02控制LED灯,74HC138芯片,74HC02芯片,74HC573芯片。
    一,硬件图解读。二,控制LED需要的74HC595程序编程。三,控制某个LED亮,其他保持不变,或者控制整8个LED,其他不变;四,读取某个LED的状态,一秒时间读取一次,如果是低电平,那么变为高电......
  • P8738 [蓝桥杯 2020 国 C] 天干地支
    题目传送门题目大意给定一个公元纪年的年份\(n\),请输出这一年的天干地支年份。解题思路将天干和地支分别存到\(a,b\)数组里;因为天干是\(10\)年一轮回,地支是\(12......
  • CF1738E Balance Addicts
    个人思路:\(sum_i\)表示前\(i\)个数的前缀和,推一下式子可知是要选若干对\(l_i,r_i\),使得\(l_1<l_2<\dots<l_k\ler_k<\dots<r_2<r_1\)且\(sum_{l_i}+......
  • 瑞芯微 | 摄像头ov13850移植笔记
    《2.Linux驱动|瑞芯微rtc-hym8563移植笔记》《3.Linux驱动|Linux内核RTC时间架构-基于瑞芯微》0、环境soc:rk3568board:EVB1-DDR4-V10软件:Android11Lin......
  • 斐波那契数python实现迭代循环两种方法
    #递归方法deffibona(n):ifn==0:return0elifn==1:return1else:returnfibona(n-1)+fibona(n-2)#结果验证pri......
  • 代码随想录算法Day23 | 669. 修剪二叉搜索树 ,108.将有序数组转换为二叉搜索树 , 538.把
    669.修剪二叉搜索树题目链接:669.修剪二叉搜索树-力扣(LeetCode)思路在删除二叉搜索树中节点值为key的节点这一题中,分五种情况来考虑,找到节点后删除即可。而这道题......
  • ASEMI高压MOS管60R380参数,60R380特征,60R380应用
    编辑-ZASEMI高压MOS管60R380参数:型号:60R380漏极-源极电压(VDS):600V栅源电压(VGS):20V漏极电流(ID):11A功耗(PD):65W储存温度(Tstg):-55to150℃静态漏源导通电阻(RDS(ON)):0.38Ω......
  • ASEMI高压MOS管60R380参数,60R380特征,60R380应用
    编辑-ZASEMI高压MOS管60R380参数:型号:60R380漏极-源极电压(VDS):600V栅源电压(VGS):20V漏极电流(ID):11A功耗(PD):65W储存温度(Tstg):-55to150℃静态漏源导通电阻(RDS(ON)):0.38Ω二极管正向......