[数据结构与算法]LeetCode509 斐波那契数

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

目录

解题思路

递归算法

代码

解题思路

递归算法

这里暴力递归就可以了。

这回终于不用打TODO标签了，通俗的说递归算法就是在自己写的方法中调用自己本身，自己调自己；递归算法的解题思路是将一个问题转化成一个 与原问题相似 但是规模更小的问题来求解，递归的优势就是可以写少量的代码来描述出解题过程中的重复计算。但是递归也有劣势，就是重复计算的东西太多了。也就是复杂度很高。如何优化？这就可以引出 分治法 和 动态规划了。请转链接：?

代码

    public static int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

?为什么简单的问题提交了这么多次？点上面的链接就知道了，哈哈哈。