单序列动态规划

最简单思路:

class Solution {
public:
    int fib(int n)
    {
        int x[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986};
        return x[n];
    }
};
class Solution {
public:
    int fib(int n)
    {
        if(n == 2 || n == 1) return 1;
        if(n <= 0) return 0;        
        return fib(n - 2) + fib(n - 1);
    }
};

加缓存:

class Solution {
private:
    map<int,int> cache;
public:
    int fib(int n)
    {        
        if(n == 2 || n == 1) return 1;
        if(n <= 0) return 0;

        int p,q;

        auto pitr = cache.find(n - 1);
        if(pitr != cache.end()){
            p = pitr->second;
        }else{            
            p = fib(n - 1);
            cache[n - 1] = p;
        }        

        auto qitr = cache.find(n - 2);
        if(qitr != cache.end()){
            q = qitr->second;
        }else{            
            q = fib(n - 2);
            cache[n - 2] = q;
        }

        return p+q;
    }
};

加缓存 + 空间优化:

class Solution {
private:
    map<int,int> cache;
public:
    int fib(int n)
    {        
        if(n == 2 || n == 1) return 1;
        if(n <= 0) return 0;

        int p,q;
        int m = 2;
        auto pitr = cache.find((n - 1) % m);
        if(pitr != cache.end()){
            p = pitr->second;
        }else{            
            p = fib((n - 1) );
            cache[(n - 1) % m] = p;
        }        

        auto qitr = cache.find((n - 2) % m);
        if(qitr != cache.end()){
            q = qitr->second;
        }else{            
            q = fib((n - 2) );
            cache[(n - 2) % m] = q;
        }

        return p+q;
    }
};

通项公式:

由于

$$ f(n+2) = f(n+1) + f(n) $$

则特征方程 $x^2 - x - 1 = 0$ 有解 $x_1 = \dfrac {1 + \sqrt []{5}}{2}$ ,$x_2 = \dfrac {1 - \sqrt []{5}}{2}$

则通解的形式为:

$$ f(n) = k_1 ({\dfrac{1 + \sqrt[]{5}}{2}})^n + k_2 ({\dfrac{1 - \sqrt[]{5}}{2}})^n $$

代入初始条件 $f (1) = f (2) = 1$

syms k1 k2 A
five = sym( 5, 'f' )
A = [
    ( (1+sqrt(five))/2 ), ( (1-sqrt(five))/2 );
    ( (1+sqrt(five))/2 )^2, ( (1-sqrt(five))/2 )^2
]
b = [1;1]
x = A \ b
A = (sym 2×2 matrix)

  ⎡ 1   √5     1   √5  ⎤
  ⎢ ─ + ──     ─ - ──  ⎥
  ⎢ 2   2      2   2   ⎥
  ⎢                    ⎥
  ⎢        2          2⎥
  ⎢⎛1   √5⎞   ⎛1   √5⎞ ⎥
  ⎢⎜─ + ──⎟   ⎜─ - ──⎟ ⎥
  ⎣⎝2   2 ⎠   ⎝2   2 ⎠ ⎦

b =

   1
   1

x = (sym 2×1 matrix)

  ⎡ √5 ⎤
  ⎢ ── ⎥
  ⎢ 5  ⎥
  ⎢    ⎥
  ⎢-√5 ⎥
  ⎢────⎥
  ⎣ 5  ⎦

因此通解为

$$ f(n) = \dfrac{1}{\sqrt[]{5}} ({\dfrac{1 + \sqrt[]{5}}{2}})^n - \dfrac{1}{\sqrt[]{5}} ({\dfrac{1 - \sqrt[]{5}}{2}})^n $$

因此代码为:

class Solution {
public:
    int fib(int n)
    {        
        if(n <= 1) return n;
        double r =  (1.0 / sqrt(5.0)) * (
             pow(( (1.0 + sqrt(5.0)) / 2.0 ), n) + 
             pow(( (1.0 - sqrt(5.0)) / 2.0 ), n) 
        );
        return round(r);
    }
};