欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode 366: Fibnacci

程序员文章站 2022-07-05 12:59:04
...

这题虽然简单,但是也容易错。
下面给出迭代的两种解法。
迭代解法1:我的版本

class Solution {
public:
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    int fibonacci(int n) {
        if (n == 1) return 0;
        if (n == 2) return 1;
        
        int a1 = 0;
        int a2 = 1;
        
        for (int i = 3; i <= n; ++i) {
            int temp = a2;
            a2 += a1;
            a1 = temp;
        }
        
        return a2;
        
    }
};

迭代解法2:九章版本

class Solution{
public:
    int fibonacci(int n) {
       int a, b;
       a = 0;
       b = 1;
       for(int i = 1; i < n; i++) {
           int c = a + b;
           a = b;
           b = c;
       }
       return a;
    }
};

这题也可以用递归+记忆化搜索做。
TBD。

相关标签: LintCode