Sword to Offer-10.1 斐波那契数列 ❀

24 Mar 2020 in Algorithm

• 题目描述：要求输入一个整数n，请你输出斐波那契数列的第n项。（从0开始，第0项为0）

• 解释：斐波那契数列

解题思路：

1、如果按照函数表达式递归计算，每次计算f(n)都要重新递归计算f(n-1)和f(n-2)的值；
2、考虑空间换时间，已计算完成的f(n)储存到一个数组里，下次计算就只要调用数组相应下标的值即可;
3、注意：要计算f(n)需要f(0)~f(n-1)一共n个值，所以数组长度为n+1；
4、注意：n=0情况要单独返回，因为要设定初值f(0)和f(1)，输入n为0时，new的数组长度为1，此时如果设定初值f(1)会报错哦。

问题图解：

AC代码：

// Fibonacci Sequence

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

补充说明：

• 注：这题和10.2，10.3类型相似，计算f(n)其实不用保存前面所有n个值，只需要保存前两个即可，具体可见10.3。

• 这里是牛客编码链接