剑指Offer第7题：斐波那契数列

发表于 更新于 分类于

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

解题思路：斐波那契数列的递推公式为f(n)=f(n-1)+f(n-2)，因此最直接的想法是直接递归来做，直接递归的话，算法的时间复杂度过大。此题可以用动态规划来解答，题目中限定了n的范围，因此可以先声明一个长度为(n+1)的数组，用来保存结果。更好的办法是，只用两个数保存结果，因为斐波那契数列的计算只跟前面两个值有关。

数组法：

1
2
3
4
5
6
7
8
9
int Fibonacci(int n) {
    if (n<=0) return 0;
    vector<int> dp(n+1, 0); //定义数组，数组中的值初始化为0
    dp[1] = 1; //第一个元素为1
    for (int i=2; i<=n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; //递推公式
    }
    return dp.back();
}
1
2
3
4
5
6
7
8
9
10
11
12
int Fibonacci(int n) {
    if (n<=0) return 0;
    if (n==1) return 1;
    int a = 0;
    int b = 1;
    while (n>0) {
        a += b; // 保存最终结果
        b = a - b; // 保存上一次的结果
        n -= 1;
    }
    return a;
}