动态规划入门-509. 斐波那契数

简介: 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:F(0) = 0,F(1) = 1F(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

一、题目描述:

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

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

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/fi…

二、思路分析:

斐波那契数的边界条件是 F(0)=0F(0)=0 和 F(1)=1F(1)=1。当 n>1n>1 时,每一项的和都等于前两项的和,我们选择使用动态规划的方法解决问题

动态规划:简称DP,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解是比较有效的。 具体解题过程:

  1. 根据重叠子问题定义状态
  2. 寻找最优子结构推导状态转移方程
  3. 确定dp初始状态
  4. 确定输出值

三、AC代码

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

四、总结:

网络异常,图片无法展示
|
掘友们,解题不易,如果觉得有用就留下个赞或评论再走吧!谢啦~ 💐



相关文章
|
存储 算法
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
蓝桥杯:递归 与 例题:斐波那契数列及优化与应用
78 0
|
1月前
动态规划——斐波那契模型
本文介绍了动态规划的基本步骤及其在几个典型问题中的应用。首先概述了动态规划的四个关键步骤:状态表示、状态转移方程、初始化及填表顺序,并说明了如何确定返回值。接着通过具体实例讲解了第 N 个泰波那契数、三步问题、使用最小花费爬楼梯以及解码方法等问题的求解过程,详细阐述了每一步的具体实现方法与代码示例。最后还讨论了如何优化初始化过程以简化编码。
26 4
动态规划——斐波那契模型
|
6月前
|
算法
动态规划求解超详细介绍 例题+代码
动态规划求解超详细介绍 例题+代码
|
5月前
|
存储 算法
精益求精——斐波那契数列的logn解法
精益求精——斐波那契数列的logn解法
61 0
动态规划| 【斐波那契数列模型 】|1137.第N个泰波那锲数
动态规划| 【斐波那契数列模型 】|1137.第N个泰波那锲数
|
算法
斐波那契数列两种算法和青蛙跳台阶的两种实际问题
当我们看到这样的题时,心想就是一个简单的递归调用么。 但是,我们要看到这种算法的不足之处——效率低下。 首先简单的介绍一下 :
93 0
|
前端开发 程序员 测试技术
斐波那契数列的多种解法
斐波那契数列的多种解法
斐波那契数列的多种解法
动态规划进阶——LeetCode53. 最大子数组的和
当遇到的元素nums[i]之前的连续数组和的最大值dp[i-1]为负数时,则不要将现在的这个数加到dp[i-1]上,因为不知道现在的这个数nums[i]是正还是负,如果盲目加上,只会无法判断其最大子数组的和,故 dp[i-1] < 0时,dp[i] = nums[i]
103 0
动态规划进阶——LeetCode53. 最大子数组的和
|
机器学习/深度学习 算法
斐波那契数列的四种解法
斐波那契数列的四种解法
斐波那契数列的四种解法