算法

测试到 fb1( 40 ) ，大于40明显卡顿

1 // 暴力方法版本
2 function fb1(n){
3   if(n==1 || n==2){ return 1;}
4   return fb1(n-1) + fb1(n-2)    
5 }

优化过的，时间复杂度明显降低

// 带记事薄的版本 - 缓存每一次计算的结果
 1 function fb2(n){
 2   var cache = [];  
 3 
 4   return helper(cache,n);  
 5 }
 6 
 7 function helper(cache,n){
 8    if(n==1 || n==2){ return 1; }
 9       
10    if(cache[n]){ return cache[n] }
11     
12    return cache[n] = helper(cache, n-1) + helper(cache,n-2)    
13 
14 }

跳出规则，从下而上计算

1 // 计算结果支持计算结果，减少重复计算 （ 注意n=0时，没有处理）
2 function fb3(n){
3     var cache = [];
4      cache[1] = cache[2] = 1;
5     for(var i=3; i<=n; i++){
6         cache[i] = cache[i-1] + cache[i-2];
7    }
8    return cache[n]  
9 }

动态规划 -- 算法设计思想

　　通过缓存记录计算结果，新的计算结果和缓存里进行对比，不断修正计算结果。

新的计算以缓存的结果为基数，不断叠加和修正。

贪婪算法 -- 算法设计思想

每一步都取当前最优解。大部分时间结果都是最优的。（局部最优）