leetcode509-斐波那契数

原题

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

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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月21日
下一篇 2020年1月21日

相关推荐

  • leetcode112-路径总和

    原题 给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:  给定如下二叉树,…

    算法 2020年1月12日
    0150
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0110
  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070
  • leetcode680-验证回文字符串II

    原题 给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。 示例 1: 输入: "aba" 输出: True 示例 2: 输入: "abca" 输出: True 解…

    算法 2020年5月19日
    0290
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode682-棒球比赛

    原题 你现在是棒球比赛记录员。给定一个字符串列表,每个字符串可以是以下四种类型之一:1. 整数(一轮的得分):直接表示您在本轮中获得的积分数。2. "+"(一轮的得…

    算法 2020年2月3日
    0210
  • 二叉树中序遍历-折纸问题

    原题(来源牛客网) 请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯…

    2020年4月27日
    02680

发表回复

登录后才能评论