509. 斐波那契数

知识点：递归；动态规划

题目描述

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

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

给你 n ，请计算 F(n) 。

示例

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

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

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

解法一：递归

这道题目可以说是大部分人的递归入门题，是一道很好的样题，之所以入门是因为题目中将结束条件和等式关系给出来了。所以比较简单。

class Solution {
    public int fib(int n) {
        if(n < 2) return n;
        return fib(n-1)+fib(n-2);
    }
}

递归算法的时间复杂度怎么计算呢，其实就是子问题个数乘以解决一个子问题需要的时间。子问题个数就是递归树中的节点总数，二叉树的节点子树是2^n, 一个子问题需要的时间，在单层里没有循环，只有加法操作，所以为1，所以整体的复杂度就是O(2^N);指数级别；

为什么会是指数级别，原因就在于有太多的重复计算。

首先要计算f20，递归调用f19，f19去调用f18，这样直到f1，然后最后一颗子树调f2，再逐层返回，最后得到f19，然后要调用f18，f18去调用f17，f17去调用f16，... ， 但是我们在算f19的时候已经都算出来了啊，什么f18，f17都有了，就像图里有的，难道还要再算一遍？递归可是耗费巨大啊，其实这就是重叠子问题！
所以我们可以用一个备忘录(dp数组)把已经好不容易算出来的结果存起来，那再算的时候如果有，就直接用就可以了。其实这就引出了动态规划，只不过我们的动规不像递归那样自顶向下(要算f20先去算f19，直至f1)，动规是自底向上，由f1得到f2，得到f3直至得到f20，所以动规脱离了递归，用for循环的迭代。

解法二：动态规划

动态规划的典型类型：
背包问题；
打家劫舍；
股票问题；
子序列问题；

动态规划常常用于求解多阶段决策问题
动态规划问题的问法：只问最优解(常和最值联系在一起)，不问具体的解；

我们先创建dp数组，首先

• 1.确定dp数组和其下标的含义；(第i个索引的斐波那契值)
• 2.确定递推公式，即状态转移方程；(题目中给出，fn=fn-1+fn-2)
• 3.dp初始化；base case; (题目中给出了)

class Solution {
    public int fib(int n) {
        int[] dp = new int[n+1];  //第i个索引的函数值为dp[i];
        if(n <= 1) return n;
        dp[0] = 0;  //base case;
        dp[1] = 1;
        for(int i = 2; i < n+1; i++){
            dp[i] = dp[i-1]+dp[i-2];  //递推公式：状态转移方程；
        }
        return dp[n];
    }
}

时间复杂度：O(N);

其实还可以进行优化，因为我们任一状态都只和前两个状态有关，所以不用维持一个这么长的数组，只需要三个变量就可以了。

class Solution {
    public int fib(int n) {
        if(n <= 1) return n;
        int pre = 0, cur = 1; //维持两个状态；
        for(int i = 2; i < n+1; i++){
            int sum = pre+cur;
            pre = cur;
            cur = sum; //状态转移
        }
        return cur;
    }
}

相关链接

代码随想录