算法基础：动态规划数组中滚动数组的使用

男娘i 2022-11-21 09:53 30阅读 0赞

这篇文章继续在前一篇文章的基础上介绍动态规划数组的优化方式。很多基础算法本来都是写给我家的小少年看的，结果发现后浪学习的速度远远超出我的想象，在一个周末用这篇文章来纪念一下吧。

### 目录 ###

*  斐波那契数列
 *  dp数组方式实现
 *  计算次数的证明
 *  动态规划法解决
 *  滚动数组的使用
 *  总结

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

# 斐波那契数列 #

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

# dp数组方式实现 #

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);
    }

详细可参看：[https://liumiaocn.blog.csdn.net/article/details/109397755][https_liumiaocn.blog.csdn.net_article_details_109397755]

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

# 计算次数的证明 #

自从发现少年已经自己会用spfa这样的东西来解决问题之后，这种基础的内容应该就不能发给他看了，所以简单确认了一下动态规划法到底解决了什么问题，为什么实际上加法的执行次数是fibonacci(n)-1，结果二十分钟左右用归纳法就证明完了，除了结尾的fib(n)-1应该是fib(n+1)-1，基本似乎是对的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]

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

# 动态规划法解决 #

后浪看完给他写的基础教程，说这还可以用滚动数组优化一下，给了个图，使用Java方式1ms计算的斐波那契45的计算结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center 1]

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

# 滚动数组的使用 #

*  第一种方式：使用&1

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

代码说明：和1进行&的操作，只会有0和1两个下标，因为此示例中使用的情况在求解的时候只是用到了n-1和n-2，这种大概是最节省的做法了，将本来长度为n的空间降到常量2.

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

*  第二种方式：使用求余

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

代码说明：和第一中方式如出一辙，但是由于第一种和1进行&的情况只有两种状态，虽然可以解决大部分问题，但是如果有三个状态需要使用的情况就会比较困难，可以考虑使用%，本质上是确认滚动时到底需要几个元素进行运算。

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

# 总结 #

看到一个之前从来没有接触过计算机的少年在繁重的大学课程学习之余1个月不到的时间从对编程一无所知到可以较为熟练使用Java和C进行滚动数组/常见排序/邻接矩阵/最短路径等算法进行实现，觉得很是欣慰和开心，真心感觉计算机算法教育实际应该从初高中开始执行比较好。

[https_liumiaocn.blog.csdn.net_article_details_109397755]: https://liumiaocn.blog.csdn.net/article/details/109397755
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e03f6a59ace04a678bf37f87891ab80d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201101085219754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg==,size_16,color_FFFFFF,t_70#pic_center