欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

斐波那契数列穷竭算法优化

程序员文章站 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);
}