侧边栏壁纸
博主头像
秦怀杂货店

纵然缓慢,驰而不息。

  • 累计撰写 145 篇文章
  • 累计创建 37 个标签
  • 累计收到 18 条评论

目 录CONTENT

文章目录

剑指Offer【6】--斐波那契数列

秦怀杂货店
2020-11-03 / 0 评论 / 0 点赞 / 527 阅读 / 0 字
温馨提示:
本文最后更新于 2020-11-03,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

[toc]

题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,第1项是1)。
n<=39

思路以及解答

斐波那契数列大家都知道:

直接暴力

思路很直接,利用函数进行递归即可。

public class Solution {
    public int Fibonacci(int n) {
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
}

重复利用结果

直接递归会造成很多重复的计算,要是我们把计算结果先存起来,使用的时候再调用,那就可以优化。

public class Solution {
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] nums = new int[n + 1];
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 2; i <= n; i++) {
            nums[i] = nums[i - 1] + nums[i - 2];
        }
        return nums[n];
    }
}
0

评论区