Yuyy
Yuyy
LeetCode509. 斐波那契数

一、介绍

  • 斐波那契数应该是动态规划的入门题,看到过很多次了。解法一般分为两种,自下而上和自上而下+备忘录(优化重复子问题)
  • 使用leetcode的idea插件
    http://bed.yuyy.info/image-20201219222722188.png

二、题目

斐波那契数,通常用 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
Related Topics
  • 数组
  • ? 181
  • ? 0
  • 三、代码

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

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode509. 斐波那契数
    一、介绍 斐波那契数应该是动态规划的入门题,看到过很多次了。解法一般分为两种,自下而上和自上而下+备忘录(优化重复子问题) 使用leetcode的idea插件 二、题目 斐波那契数,通…
    扫描二维码继续阅读
    2020-12-19
    友情链接
    标签
    文章归档
    近期文章