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：

输入：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\leq N\leq30\)

Reference

题解

递归

基本思路： 使用一个数组存放历史结果，加速递归计算

代码如下：

int fib_cache(int N, int **cache, int *lenCache, int *fullCache){
    if (!N)
        return 0;
    if (!(*cache))
    {
        *lenCache = 2;
        *fullCache = N + 1;
        *cache = (int *)memset(malloc(sizeof(int) * *fullCache), 0, sizeof(int) * *fullCache);
        (*cache)[0] = 1;
        (*cache)[1] = 1;
    }
    if (N > *lenCache && N <= *fullCache)
        (*cache)[N-1] = fib_cache(N - 1, cache, lenCache, fullCache) + fib_cache(N - 2, cache, lenCache, fullCache);
        *lenCache = N;
    return (*cache)[N - 1];
}

int fib(int N){
    int *cache = NULL, lenCache = 0, fullCache = 0;
    return fib_cache(N, &cache, &lenCache, &fullCache);
}

迭代

基本思路： 根据定义推算斐波那契数

代码如下：

int fib(int N){
    int ret = 0, next = 1, tmp;
    while (N)
    {
        tmp = ret;
        ret = next;
        next = ret + tmp;
        N--;
    }
    return ret;
}

评论