【LeetCode】509. 斐波那契数

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);指数级别;

为什么会是指数级别,原因就在于有太多的重复计算。
【LeetCode】509. 斐波那契数

首先要计算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;
    }
}

相关链接

代码随想录

上一篇:栈和递归---斐波那契数列的非递归实现


下一篇:fib