首页 > 其他分享 >509_斐波那契数

509_斐波那契数

时间:2024-10-23 14:34:59浏览次数:3  
标签:契数 数列 int 斐波 509 那契 dp 数字

509_斐波那契数

【问题描述】

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

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

给定 n ,请计算 F(n)

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 0 <= n <= 30

【算法设计思想】

本题可以看作是入门动态规划的经典第一题。

  1. 定义状态
    • 状态是指问题的一个特定阶段的状态。对于斐波那契数列,状态可以定义为 dp[i],表示斐波那契数列的第 i 个数字。
  2. 确定状态转移方程
    • 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于斐波那契数列,状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2],表示第 i 个斐波那契数等于前两个斐波那契数之和。
  3. 初始化
    • 初始化一些基本情况,以便开始递推计算。对于斐波那契数列,初始化 dp[0] = 0dp[1] = 1
  4. 确定计算顺序
    • 确定状态的计算顺序,通常是从已知状态逐步推导到最终状态。对于斐波那契数列,计算顺序是从 dp[0]dp[1] 开始,逐步计算到 dp[n]
  5. 返回结果
    • 最后返回所需的最终结果。对于斐波那契数列,返回 dp[n]

【算法描述】

C++:

class Solution {
public:
    // 计算斐波那契数列的第n个数字
    int fib(int n) {
        // 如果n为0,直接返回0,因为斐波那契数列的第一个数字是0
        if (n == 0)
            return 0;

        // 创建一个数组来存储斐波那契数列中的前n+1个数字
        int dp[n + 1];

        // 初始化斐波那契数列的前两个数字
        dp[0] = 0; // 第0个数字是0
        dp[1] = 1; // 第1个数字是1

        // 使用循环计算从第2个到第n个斐波那契数
        for (int i = 2; i <= n; i++) {
            // 每个斐波那契数等于它前面两个斐波那契数之和
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回计算得到的第n个斐波那契数
        return dp[n];
    }
};

Java:

class Solution {
    // 定义一个公共方法fib,用于计算斐波那契数列的第n个数字
    public int fib(int n) {
        // 如果n为0,根据斐波那契数列的定义,返回0
        if (n == 0) return 0;

        // 创建一个长度为n+1的数组dp,用于存储斐波那契数列中从第0个到第n个数字
        int[] dp = new int[n + 1];

        // 初始化斐波那契数列的前两个值
        dp[0] = 0; // 根据定义,斐波那契数列的第0个数字是0
        dp[1] = 1; // 根据定义,斐波那契数列的第1个数字是1

        // 从第2个数字开始,利用动态规划的思想计算每个斐波那契数
        for (int i = 2; i <= n; i++) {
            // 当前位置的斐波那契数等于前两个斐波那契数之和
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回斐波那契数列的第n个数字
        return dp[n];
    }
}

Python:

class Solution:
    def fib(self, n: int) -> int:
        # 如果n为0,根据斐波那契数列的定义,返回0
        if n == 0:
            return 0
        
        # 初始化dp列表,使用列表推导式来创建一个包含n+1个元素的列表,所有元素初始值都为0
        dp = [0] * (n + 1)

        # 根据斐波那契数列的定义,设置dp[0]和dp[1]的值
        dp[0] = 0
        dp[1] = 1

        # 从第2个数字开始,使用动态规划计算斐波那契数列中的每一个数字
        for i in range(2, n + 1):
            # 当前位置的斐波那契数等于前两个斐波那契数之和
            dp[i] = dp[i - 1] + dp[i - 2]

        # 返回斐波那契数列的第n个数字
        return dp[n]

C:

int fib(int n) {
    // 如果n为0,根据斐波那契数列的定义,返回0
    if(n == 0) return 0;

    // 创建一个大小为n+1的数组dp,用于存储斐波那契数列中从第0个到第n个数字
    int dp[n + 1];

    // 初始化斐波那契数列的前两个值
    dp[0] = 0; // 第0个数字是0
    dp[1] = 1; // 第1个数字是1

    // 从第2个数字开始,使用动态规划计算斐波那契数列中的每一个数字
    for(int i = 2; i <= n; i++) {
        // 当前位置的斐波那契数等于前两个斐波那契数之和
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    // 返回斐波那契数列的第n个数字
    return dp[n];
}

标签:契数,数列,int,斐波,509,那契,dp,数字
From: https://www.cnblogs.com/zeta186012/p/18496307

相关文章

  • 斐波拉契数列
    从0开始,如:0,1,1,2,3,5,8…#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//递归实现intFib(intx){if(x<=0){return0;}elseif(x>2){returnFib(x-1)+Fib(x-2);}elseif(x<=2&&......
  • NOIP模拟赛(10.17):语言,色球,斐波,偶数
    语言题面:牛妹正在学习一种新的语言,在这种语言里,单词只有形容词(\(\texttt{A}\)),名词(\(\texttt{N}\))和动词(\(\texttt{V}\))三种词性。但是一个单词可以对应多种词性。一个名词性词组(\(\texttt{NP}\))可以由一个名词(\(\texttt{N}\)),或者一个形容词修饰一个子名词性词组(\(\texttt{A}+......
  • 【算法】动态规划:从斐波那契数列到背包问题
    【算法】动态规划:从斐波那契数列到背包问题文章目录【算法】动态规划:从斐波那契数列到背包问题1.斐波那契数列2.爬楼梯3.零钱转换Python代码4.零钱兑换II5.组合数dp和排列数dp6.为什么动态规划的核心思想计算组合数的正确方法代码实现为什么先遍历硬币再遍历金额可以......
  • 代码随想录算法训练营 | 动态规划,509. 斐波那契数,70. 爬楼梯, 746. 使用最小花费爬楼梯
    动态规划:1.动态规划中每一个状态一定是由上一个状态推导出来的2.确定dp数组(dptable)以及下标的含义,确定递推公式dp,数组如何初始化,确定遍历顺序,举例推导dp数组;3.Debug:dp数组打印509.斐波那契数题目链接:509.斐波那契数文档讲解︰代码随想录(programmercarl.com)视频讲解︰斐波那......
  • Day 28 动态规划part01| LeetCode 509.斐波那契数,70.爬楼梯,746.使用最小花费爬楼梯
    理论基础包含题目类别:基础类(斐波那契、爬楼梯)、背包问题、打家劫舍、股票问题、子序列问题解题关键DP数组定义以及下标的含义递推公式DP数组如何初始化遍历顺序打印DP数组509.斐波那契数509.斐波那契数classSolution{publicintfib(intn){......
  • 一本通 1071:菲波那契数
    【题目描述】菲波那契数列是指这样的数列:数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。给出一个正整数k,要求菲波那契数列中第k个数是多少。【输入】输入一行,包含一个正整数k。(1≤k≤46)【输出】输出一行,包含一个正整数,表示菲波那契数列中第k个数的大小......
  • 信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重
    PDF文档公众号回复关键字:202410041P7074[CSP-J2020]方格取数[题目描述]设有n×m的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中......
  • P8808 [蓝桥杯 2022 国 C] 斐波那契数组
    Hello大家好,我是小亦,今天一大早就来更东西了嘿嘿,不知道现在大家有没有回老家的或去玩的,那有没有扎在家的,呜呜呜我就是宅在家的QWQ,唉没办法啊,好那么好不了这些了qwq,今天我来讲的题目是来自蓝桥杯2022年国C题目也就是第三道题,名叫:斐波那契数组,其实这道题呢,嗯比较的难所以呢我也......
  • x509: cannot validate certificate for 192.168.0.56 because it doesn't contain an
    containerd里无法拉取镜像无法从私建的harbor上拉取报错FATA[0000]pullingimage:rpcerror:code=Unknowndesc=failedtopullandunpackimage x509:cannotvalidatecertificatefor192.168.0.56becauseitdoesn'tcontainanyIPSANs 若是配置之后还是一直报x5......
  • 洛谷题单指南-分治与倍增-P3509 [POI2010] ZAB-Frog
    原题链接:https://www.luogu.com.cn/problem/P3509题意解读:n个点,每个点上有一只青蛙每次跳到距离自己第k近的点,m次之后跳到哪个点。解题思路:1、计算距离每个点第k近的点,存入ne[N]给定一个点i,距离i第k近的点一定在长度为k+1个点的窗口内,窗口包括i并且,第k近的点只能是左端点或者......