单序列动态规划
最简单思路：
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);
}
};