作者：hackett
微信公众号：加班猿
斐波那契数列
问题构造形容的数学模式：
一、暴力递归解法
int fib(int n)
{if(n == 1 || n == 2)
return 1;
return fib(n -1) + fib(n - 2);
}解析：代码尽管简洁，然而效率非常低下，算法的工夫复杂度为 O(), 指数级别，爆炸（通过递归树能够看出这个解法还存在 重叠子问题）
二、备忘录递归解法
用一个一维数组（哈希表、字典）充当这个「备忘录」
int fib(int n)
{if(n < 1)
return 0;
vector<int> memo(n+1,0); // 初始化备忘录为 0
return calc(memo,n); // 初始化最简状况
}
int calc(vector<int>& memo,int n)
{if(n == 1 || n == 2)
return 1;
// 计算
if(memo[n] != 0)
return memo[n];
memo[n] = calc(memo,n-1) + calc(memo,n-2);
return memo[n];
}解析：每次算出某个⼦问题的答案后别急着返回，先记到「备忘录」⾥再返回；每次遇到⼀个⼦问题先去「备忘录」⾥查，⼀查，如果发现之前曾经解决过这个问题了，间接把答案拿进去⽤，不要再 耗时去计算了
算法的工夫复杂度为 O(n)，比起暴力解法，降了一个维度，「⾃顶向下」模式
三、数组的迭代解法
有了第二的「备忘录」启发，咱们将它独立进去成为一张表，在这边表上实现「⾃底向上」
int fib(int n)
{vector<int> db(n+1,0); // 初始化
db[1] = 1;
db[2] = 1;
for(int i = 3 ; i < n ; i++)
db[i] = db[i-1] + db[i-2]
return db[n];
}上述的操作 return fib(n -1) + fib(n – 2)，db[i] = db[i-1] + db[i-2]，都是围绕这个⽅程式的不同表现形式。可⻅列出「状态转移⽅程」的重要性，它是 解决问题的核⼼。所以，进一步优化把空间复杂度降为 O(1)
int fib(int n)
{if(n == 1 || n == 2)
return 1;
int prev = 1,curr = 1;
for(int i = 3 , i < n ; i++)
{
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}解析：动静布局问题最艰难的就是写出状态转移⽅程，即下面的暴力解。
依据斐波那契数列的状态转移方程，以后状态只和之前的两个状态无关，其实并不需要那么⻓的⼀个 db 表来存储所有的状态，只有想方法存储之前的两个状态就⾏了
如果你感觉文章还不错，记得 ”点赞关注“
关注我的微信公众号【加班猿】能够获取更多内容