斐波那契数列穷竭算法优化
程序员文章站
2022-04-08 12:59:43
...
int fib(int n){
if(n<=1) return n;
return fib(n-1)+fib(n-2);
}
在斐波那契数列中,如果fib(n)的n是一定的,无论多少次调用都会得到同样的结果。因此如果计算一次后,用数列将其存储起来,便可优化之后的计算。例如下图在计算fib(10)时同样的n被计算了很多次,因此可以获得很大的优化空间。这种方法是出于记忆化搜索或者动态规划的想法,之后我们会介绍。
int memo[MAX_N + 1];
int fib(int n){
if(n<=1) return n;
if(memo[n] != 0) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
上一篇: sklearn 决策树可视化