Ricky.L的随笔
0%

LeetCode.509. 斐波那契数（简单）

发表于 更新于 分类于 Disqus：

题目

LeetCode.509. 斐波那契数（简单）

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

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

题解

解法1：记忆化递归

根据定义，可以直接写出递归式，最简单。
但是递归会有很多重叠子问题，重复计算很耗时。

可以想象出函数调用的递归树，F(n)总共调用次数就是树的节点数。
从F(n)到F(n - 1)一直分解到F(1)，这样逐一递减，一共n层递归树。
第i层(从上到下数)节点数为2的i次方，递归树总节点数为 2的0次方 + 2的1次方 + 2的2次方 + …… + 2的n - 1次方，等比数列求和为2的n次方。递归求解的时间复杂度为O(2^n)。

把会重复使用到的计算结果记下来，每一项只计算一次，时间复杂度降低为线性。
自上而下做动态规划。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    fun fib(n: Int): Int {
        val memo = IntArray(n + 1) { -1 }
        fun f(n: Int): Int {
            if (n == 0) return 0
            if (n == 1) return 1
            if (memo[n] != -1) return memo[n]
            memo[n] = f(n - 1) + f(n - 2)
            return memo[n]
        }
        return f(n)
    }
}

解法2：自下而上的动态规划

直接根据公式递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    fun fib(n: Int): Int {
        if (n == 0) return 0
        if (n == 1) return 1
        var prepre = 0
        var pre = 1
        var cur = 0
        for (i in 2..n) {
            cur = prepre + pre
            prepre = pre
            pre = cur
        }
        return cur
    }
}