Leetcode 509 斐波那契数

2023-12-28 21:58:56

题意理解

? ? ? ? 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。

? ? ? ? 其满足递推公式:
????????????????F(0) = 0,F(1) = 1
????????????????F(n) = F(n - 1) + F(n - 2),其中 n > 1

? ? ? ? 目标:求第n个斐波那契数是多少?

解题思路

? ? ? ? 这道题可以采用动态规划的思路来解决,解决动态规划的题目,一般可以按照五个步骤来分析。

? ? ? ? 首先:驱动dp数组就下标的含义:dp[i]表示第i个斐波那契数是dp[i]

? ? ? ? 其次:初始化,根据斐波那契数列可知:dp[0]=1, dp[1]=1

? ? ? ? 再有:确定递推公式,即斐波那契数的定义:F(n) = F(n - 1) + F(n - 2)

? ? ? ? 最后:确定遍历顺序,斐波那契数总是受它前面的连个数影响,所以,我们总是从前往后的顺序遍历。

? ? ? ? 最后的一个步骤用于debug,打印dp数组,用于验证思路的正确性。

1.动态规划解题

public int fib(int n) {
        //定义dp数组
        int[] dp=new int[n+1];
        //初始化
        dp[0]=0;
        if(n>0) dp[1]=1;//n=0时。
        //遍历
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

2.存储压缩

之前我们采用dp[]数组来存储,但是实际上,最终的结果只需要一个值。

我们对原来的dp[]数组存储空间进行压缩。sum表示dp0+dp1的和。

在将其不断后移:dp0=dp1,dp1=sum,sum=dp0+dp1, 最终获得第n个斐波那契数由sum返回。

空间复杂度:O(n+1)——>O(3)

public int fib(int n) {
        //定义dp数组
        int sum=0;
        int dp0=0,dp1=1;
        //初始化
        if(n==0) return sum;//n=0时。
        sum=dp0+dp1;
        //遍历
        for(int i=2;i<=n;i++){
            sum=dp0+dp1;
            dp0=dp1;
            dp1=sum;
        }
        return sum;
    }

3.分析?

时间复杂度:O(n) 时间耗费在遍历n个斐波那契数

空间复杂度

? ? ? ? O(n):使用dp数组时

? ? ? ? O(1):使用单个值来存储结果时。

n表述出入数字的大小

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135268955
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。