leetcode-509：菲波那切数列

问题

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

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

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

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

思路

通过这道题目让大家可以初步认识到，按照动规五部曲是如何解题的

对于动规，如果没有方法论的话，可能简单题目可以顺手一写就过，难一点就不知道如何下手了

所以我总结的动规五部曲，是要用来贯穿整个动态规划系列的，就像之前讲过二叉树系列的递归三部曲，回溯法系列的回溯三部曲一样。后面慢慢大家就会体会到，动规五部曲方法的重要性

动态规划

动规五部曲：
这里我们要用一个一维dp数组来保存递归的结果

• 确定dp数组以及下标的含义

  • dp[i]的定义为：第i个数的斐波那契数值是dp[i]

• 确定递推公式

  • 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

• dp数组如何初始化

  • dp[0] = 0;
  • dp[1] = 1;

• 确定遍历顺序

  • 从递归公式dp[i] = dp[i - 1] + dp[i - 2]中可以看出，dp[i]是依赖dp[i - 1]和dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

• 举例推导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){
       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];
    }
    }

• 时间复杂度：

• 空间复杂度：

当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列

class Solution {
    public int fib(int n) {
        if (n <= 1) 
            return n;
        int[] dp = new int[n + 2];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
}

• 时间复杂度：
• 空间复杂度：

递归解法

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

时间复杂度：
空间复杂度： 算上了编程语言中实现递归的系统栈所占空间