滚动数组的作用在于优化空间,主要应用在递推或动态规划中(如01背包问题)。因为DP题目是一个自底向上的扩展过程,我们常常需要用到的是连续的解,前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。
一个简单的例子:
斐波那契数列:
一般代码:
利用滚动数组优化后代码为:
滚动数组实际是一种节省空间的办法,时间上没啥优势,多用于DP中,举个例子吧:
一个DP,平常如果需要1000×1000的空间,其实根据DP的无后效性,可以开成2×1000,然后通过滚动,获得和1000×1000一样的效果。滚动数组常用于DP之中,在DP过程中,我们在由一个状态转向另一个状态时,很可能之前存储的某些状态信息就已经无用了,例如在01背包问题中,从理解角度讲我们应开DP[i][j]的二维数组,第一维我们存处理到第几个物品,也就是阶段了,第二维存储容量,但是我们获得DP[i],只需使用DP[i - 1]的信息,DP[i - k],k>1都成了无用空间,因此我们可以将数组开成一维就行,迭代更新数组中内容,滚动数组也是这个原理,目的也一样,不过这时候的问题常常是不可能缩成一维的了,比如一个DP[i][j]需要由DP[i
- 1 ][k],DP[i - 2][k]决定,i<n,0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组,结果很明显,超内存,其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定,空间复杂度差别巨大。
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1757060
主要介绍了Java滚动数组计算编辑距离操作,涉及java字符串与数组的遍历、计算、转换等相关操作技巧,需要的朋友可以参考下
[二维数组](https://so.csdn.net/so/search?q=%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84&spm=1001.2101.3001.7020)及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组...
1.《算法设计技巧与分析》的课堂内容c源码实现 2.编译环境vc6.0 3.关键代码有详细的注释描述
用滚动数组实现最大路径问题
斐波那契数列的几种时间复杂度优化 以下代码因不同算法而时间复杂度不同个人归类为不同版本,总结...3.以下利用到了动态规划的滚动数组。 4.用位运算来代替乘法、除法以及取模。 5.有数学公式用数学公式@.@....
代码实现(滚动数组优化)dp := 0 // 用一个值当做滚动数组使用i := -1 // i表示前面最近的s[j]==s[i]的位置if dp < j-i {
labview实现2D数组滚动显示。
题目:309. 最佳买卖股票时机含冷冻期滚动数组:
tag上是分层图+矩阵优化,但是被我用暴力+滚动数组水过去了(赞美O2!)对每个点有三种状态,0:上一秒已经在这个城市了;1:这一秒刚到;2:自爆。只需要记录最后时刻0、1的和以及所有时刻2的和即可,注意滚动数组...
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
二分法、回溯法、剪枝DFS、BFS、动态规划、位运算、数学、大数、排列有限状态自动机、排序、归并排序、归并思想、滚动数组优化、双指针、分治法二叉树遍历、问题抽象、递归、俄罗斯农民乘法、滑动窗口、约瑟夫环、双...
javascript读取json数组生成滚动分页 javascript读取json数组生成滚动分页 javascript读取json数组生成滚动分页
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 题解 数组篇 二. 字符串 题目分类 题
CC--面试问题来自各种编程专家的算法问题的解决方案,包括LeetCode,LintCode和Hackerrank(过去的Interview Street)。LeetCode示例std:sort +自定义cmp: 。... DP:通过滚动数组进行优化: 。 DP:最小解
二维数组及滚动数组: 118, 119, 661, 598, 419 数组的旋转: 189, 396 特定顺序遍历二维数组: 54, 59, 498 二维数组变换: 566, 48, 73, 289 前缀和数组: 303, 304, 238 字符串 位运算 栈与递归 链表 哈希表 贪心算法 ...
1.4.二维数组及滚动数组 题号 描述 状态 1.5.数组的旋转 题号 描述 完成状态 1.6.特定顺序遍历二维数组 题号 C++11 完成状态 1.7.二维数组变换 题号 描述 完成状态 1.8.前缀和数组 题号 描述 完成状态 模板题-前缀和...
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 二. 字符串 题目分类 题目编号 字符 520 回文串的...
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 链表类: 文章:https://mp.weixin.qq.com/s/vK0JjSTHfpA
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 题解 数组篇 二. 字符串 题目分类 题目编号 字符 ...