原题
斐波那契数，通常用 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.
提示：
0 ≤ N ≤ 30
解法
思想
递归，由于很多递归单元会被重复计算，需要做缓存。
代码
class Solution {
Integer[] cache = new Integer[30];
public int fib(int N) {
if(N == 0) return 0;
if(N == 1) return 1;
if(cache[N-1]!=null){
return cache[N-1];
}
int ans = fib(N-1)+fib(N-2);
cache[N-1] = ans;
return ans;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode509-%e6%96%90%e6%b3%a2%e9%82%a3%e5%a5%91%e6%95%b0/
相关推荐
-
leetcode45-跳跃游戏II
原题 原题 给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输...
-
leetcode80-删除排序数组中的重复项II
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外...
-
leetcode131-分割回文串
原题 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ...
-
leetcode206-反转链表
原题 反转一个单链表。 示例： 输入： 1->2->3->4->5->NULL 输出： 5->4->3->2->1->NULL 进阶： 你可以迭代或递归地反转链表。你能否用两种方法...
-
leetcode876-链表的中间结点
原题 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1: 输入： [1,2,3,4,5] 输出： 此列表中的结...
-
leetcode16-最接近的三数之和
原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存...
-
leetcode24-两两交换链表中的节点
原题 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->...
-
用一个栈实现另一个栈的排序
原题（来源牛客网） 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？ 解法 ...
-
leetcode95-不同的二叉搜索树II
原题 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: [ [1,null,3,2], &n...
-
leetcode374-猜数字大小
原题 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接...
