509. 斐波那契数


509. 斐波那契数

斐波那契数,通常用 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.

动态规划

class Solution {
    public int fib(int n) {
        if (n < 2) &#123;
            return n;
        &#125;
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) &#123;
            p = q;
            q = r;
            r = p + q;
        &#125;
        return r;
    &#125;

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/

&#125;

递归

    public int fib(int n) &#123;
        if (n == 0 || n == 1)&#123;
            return n;
        &#125;else &#123;
            return fib(n-1)+fib(n-2);
        &#125;
    &#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
704. 二分查找 704. 二分查找
704. 二分查找给定一个  n  个元素有序的(升序)整型数组  nums 和一个目标值  target  ,写一个函数搜索  nums  中的 target,如果目标值存在返回下标,否则返回 -1。 class Solution &am
2021-02-27 future
下一篇 
557. 反转字符串中的单词 III 557. 反转字符串中的单词 III
557. 反转字符串中的单词 III难度简单 274给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。示例:输入:“Let’s take LeetCode contest”输出:“s’teL ekat e
2021-02-27 future
  目录