LeetCode-509. 斐波那契数

阳光穿透心脏的1/2处 2024-03-26 16:14 87阅读 0赞

题目来源  
[509. 斐波那契数][509.]

### 动态规划 ###

动规五部曲：

*  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\];中可以看出，dp\[i\]是依赖 dp\[i - 1\] 和 dp\[i - 2\]，那么遍历的顺序一定是从前到后遍历的

*  5.举例推导dp数组

按照这个递推公式dp\[i\] = dp\[i - 1\] + dp\[i - 2\]，我们来推导一下，当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;
            }
            int[] dp = new int[n+1];
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2;i<=n;i++){
        
                dp[i] = dp[i-1] + dp[i-2];
            }
            return dp[n];
        }
    }

![在这里插入图片描述][6ca5bd60a39c437b85e40a13a2acc73d.png]

[509.]: https://leetcode.cn/problems/fibonacci-number/
[6ca5bd60a39c437b85e40a13a2acc73d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/9920d176e5534fe8b7862fe8ad5edfe3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，87人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-509. 斐波那契数

题目来源 [509. 斐波那契数][509.] 动态规划动规五部曲： 1.确定dp数组以及下标的含义 dp\[i\]的定义为：第i个数的斐波那契数值是d

阳光穿透心脏的1/2处/ 2024年03月26日 16:14/ 0 赞/ 88 阅读

相关 509. 斐波那契数

509. 斐波那契数题干描述动态规划五部曲 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如

朴灿烈づ我的快乐病毒、/ 2023年10月16日 15:50/ 0 赞/ 25 阅读

相关动态规划——509. 斐波那契数

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

约定不等于承诺〃/ 2023年10月08日 16:16/ 0 赞/ 28 阅读

相关 leetcode 509. 斐波那契数（Java版）

题目 [https://leetcode-cn.com/problems/fibonacci-number/][https_leetcode-cn.com_problem

港控/mmm°/ 2023年01月21日 03:28/ 0 赞/ 87 阅读

相关 509. 斐波那契数

参考： [面试题10- I. 斐波那契数列][10- I.] [10- I.]: https://blog.csdn.net/zyx_ly/article/detai

朴灿烈づ我的快乐病毒、/ 2022年12月12日 02:18/ 0 赞/ 189 阅读

相关（js）leetcode 509. 斐波那契数

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

比眉伴天荒/ 2022年10月25日 12:57/ 0 赞/ 168 阅读

相关 509. 斐波那契数

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

太过爱你忘了你带给我的痛/ 2022年10月07日 07:50/ 0 赞/ 191 阅读

相关 leetcode 509 斐波那契数

前言题目：[509. 斐波那契数][509.] 参考题解：[斐波那契数-代码随想录][-] -------------------- 提交代码拿到这道题目

ゝ一纸荒年。/ 2022年09月16日 05:50/ 0 赞/ 210 阅读

相关 509 斐波那契数（递推）

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

秒速五厘米/ 2022年08月30日 00:48/ 0 赞/ 200 阅读

相关 leetcode:509 .斐波那契数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

柔情只为你懂/ 2022年02月13日 05:06/ 0 赞/ 247 阅读