算法基础：从斐波那契数列的计算理解动态规划数组的作用

蔚落 2022-11-21 09:41 22阅读 0赞

这篇文章以Fibonacci数列计算的递归实现使用动态规划法的优化为例，对动态规划方式所能起到的作用进行说明。

### 目录 ###

*  斐波那契数列
 *  简洁的递归实现
 *  递归执行效率分析
 *  效率低下的原因
 *  优化方式1: 引入dp数组
 *  优化方式2: 直接生成dp数组
 *  总结

--------------------

# 斐波那契数列 #

> 斐波那契数列:  
> f(n) = f(n-1) + f(n-2) (n>1)  
> f(0) = 1  
> f(1) = 1

# 简洁的递归实现 #

斐波那契的实现非常简单，尤其是使用递归来写，这几乎是递归理解时的一个入门算法，实现示例可能会如下所示：

int fibonacci(int n) {
        if(n == 0 || n == 1) return 1;
        return fibonacci(n-1) + fibonacci(n-2);
    }

这样写实际上是有很多限制的，首先它执行不了多少次，n为46的时候就会int型溢出了，但是这并不是这篇文章要纠结的地方，在后面将会重点分析一下其执行效率。

--------------------

# 递归执行效率分析 #

使用clock函数来计算一下n为45的时候所需要的时间，整体示例代码如下所示：

#include <stdio.h>
    #include <time.h>
    
    int fibonacci(int n) { 
        if(n == 0 || n == 1) return 1;
        return fibonacci(n-1) + fibonacci(n-2);
    }
    
    int main() { 
        int n = 0;
        while(~scanf("%d",&n)) { 
            time_t start_time=0, end_time=0;
            start_time=clock();
            printf("fibonacci(%d)=%d\n",n,fibonacci(n));
            end_time=clock();
            printf("Time Used: %f\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
        }
        return 0;
    }

*  执行时间如下所示

45
    fibonacci(45)=1836311903
    Time Used: 9.107935

虽然这乍一看超出了我们的想象，仔细一想，这毕竟是一个指数级别，花这么多时间也不足为奇了。

--------------------

# 效率低下的原因 #

这里我们引入一个全局变量用来计算加法执行的次数

#include <stdio.h>
    #include <time.h>
    
    int add_operation_count = 0;
    
    int fibonacci(int n) {
        if(n == 0 || n == 1) return 1;
        add_operation_count++;
        return fibonacci(n-1) + fibonacci(n-2);
    }
    
    int main() {
        int n = 0;
        while(~scanf("%d",&n)) {
            add_operation_count=0;
            time_t start_time=0, end_time=0;
            start_time=clock();
            printf("fibonacci(%d)=%d\n",n,fibonacci(n));
            end_time=clock();
            printf("Time Used: %f\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            printf("add_operation_count: %d\n",add_operation_count);
        }
        return 0;
    }

执行结果如下，可以看到有大量的重复计算。

45
    fibonacci(45)=1836311903
    Time Used: 9.324074
    add_operation_count: 1836311902

# 优化方式1: 引入dp数组 #

此处我们引入一个dp数组用来保存已经计算过的值，这样就不必再重复计算。

#include <stdio.h>
    #include <time.h>
    #include <string.h>
    
    #define FIBONACCI_MAX 1000
    int add_operation_count = 0;
    int dp[FIBONACCI_MAX] = {  0 };
    
    int fibonacci(int n) { 
        if(n == 0 || n == 1) { 
            dp[n]= 1; return dp[n];
        }
        if (dp[n] != -1) return dp[n];
        dp[n] = fibonacci(n-1) + fibonacci(n-2);
        add_operation_count++;
        return dp[n];
    }
    
    int main() { 
        int n = 0;
        while(~scanf("%d",&n)) { 
            add_operation_count=0;
            memset(dp,-1,sizeof(int)*FIBONACCI_MAX);
            time_t start_time=0, end_time=0;
            start_time=clock();
            printf("fibonacci(%d)=%d\n",n,fibonacci(n));
            end_time=clock();
            printf("Time Used: %f\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            printf("add_operation_count: %d\n",add_operation_count);
        }
        return 0;
    }

这种方式之下，需要进行+计算的次数会剧降至n-1次，因量变引起的质变的优化效果在执行时间上也可以清晰地看出来，从9秒降到了毫秒以下：

45
    fibonacci(45)=1836311903
    Time Used: 0.000050
    add_operation_count: 44

当然利用C语言的特性上述函数还可以进行如下更加简洁的写法，只是一些无关痛痒的小技巧了，另外用不到的全局变量也可以删除。

int fibonacci(int n) { 
        if (n == 0 || n == 1) return dp[n]=1;
        if (dp[n] != -1) return dp[n];
        return dp[n]=fibonacci(n-1)+fibonacci(n-2);
    }

# 优化方式2: 直接生成dp数组 #

不需要使用递归了，正向计算一次就直接算出返回值了，这也是很多dp数组使用的常见套路。示例代码如下（注意下标未做过多异常判断）

int fibonacci(int n) { 
        dp[0]=1,dp[1]=1;
        for (int i=2; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }

执行示例如下所示

#include <stdio.h>
    #include <time.h>
    #include <string.h>
    
    #define FIBONACCI_MAX 1000
    int dp[FIBONACCI_MAX] = {  0 };
    
    int fibonacci(int n) { 
        dp[0]=1,dp[1]=1;
        for (int i=2; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
    
    int main() { 
        int n = 0;
        while(~scanf("%d",&n)) { 
            memset(dp,0,sizeof(int)*FIBONACCI_MAX);
            time_t start_time=0, end_time=0;
            start_time=clock();
            printf("fibonacci(%d)=%d\n",n,fibonacci(n));
            end_time=clock();
            printf("Time Used: %f\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
        }
        return 0;
    }

# 总结 #

这篇文章以最基础的斐波那契数列为例介绍了动态数组在使用上的优化效果。