Leetcode 509 斐波那契数

题意理解：

? ? ? ? 斐波那契数 （通常用 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表述出入数字的大小