- 浏览: 533815 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (231)
- 一个操作系统的实现 (20)
- 汇编(NASM) (12)
- Linux编程 (11)
- 项目管理 (4)
- 计算机网络 (8)
- 设计模式(抽象&封装) (17)
- 数据结构和算法 (32)
- java基础 (6)
- UML细节 (2)
- C/C++ (31)
- Windows (2)
- 乱七八糟 (13)
- MyLaB (6)
- 系统程序员-成长计划 (8)
- POJ部分题目 (10)
- 数学 (6)
- 分布式 & 云计算 (2)
- python (13)
- 面试 (1)
- 链接、装载与库 (11)
- java并行编程 (3)
- 数据库 (0)
- 体系结构 (3)
- C++ template / STL (4)
- Linux环境和脚本 (6)
最新评论
-
chuanwang66:
默默水塘 写道typedef void(*Fun)(void) ...
C++虚函数表(转) -
默默水塘:
typedef void(*Fun)(void);
C++虚函数表(转) -
lishaoqingmn:
写的很好,例子简单明了,将观察者模式都表达了出来。
这里是ja ...
观察者模式——Observer
转载:http://blog.csdn.net/niushuai666/article/details/6677982
滚动数组的作用在于优化空间,主要应用在递推或动态规划中(如01背包问题)。因为DP题目是一个自底向上的扩展过程,我们常常需要用到的是连续的解,前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。
一个简单的例子:
斐波那契数列:
一般代码
#include<iostream> #include<cstdio> using namespace std; int Fib[25]; int fib(int n) { Fib[0] = 0; Fib[1] = 1; Fib[2] = 1; for(int i = 3; i <= n; ++i) Fib[i] = Fib[i - 1] + Fib[i - 2]; return Fib[n]; } int main() { int ncase, n, ans; scanf("%d", &ncase); while(ncase--) { scanf("%d", &n); ans = fib(n); printf("%d\n", ans); } return 0; }
利用滚动数组优化后代码为:
#include <iostream> #include <cstdio> using namespace std; int Fib[3]; int fib(int n){ if(n==0) return 0; if(n==1) return 1; Fib[0]=0; Fib[1]=1; for(int i=2;i<=n;i++){ Fib[2]=Fib[0]+Fib[1]; Fib[0]=Fib[1]; Fib[1]=Fib[2]; } return Fib[1]; } int main(){ int ncase, n, ans; scanf("%d", &ncase); while(ncase--) { scanf("%d", &n); //需要引入<cstdio> ans = fib(n); printf("%d\n", ans); //需要引入<cstdio> } return 0; system("pause"); //需要引入<iostream> return 0; }
滚动数组实际是一种节省空间的办法,时间上没啥优势,多用于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]决定,空间复杂度差别巨大
推荐题目:
POJ1159
POJ1717
POJ1745
发表评论
-
快排备忘
2013-10-26 11:27 550http://hi.baidu.com/pluto455988 ... -
LRU简单实现C++
2013-10-17 10:52 3976页面置换算法: 在地址映射过程中,若在页面中发现所要访问的页 ... -
二叉树相关
2013-10-04 17:40 692本节主要是为了写二叉树类型题目练手的代码,重点培养运用“指针 ... -
双指针策略(《编程之美》3.5 最短摘要生成)
2013-03-26 15:17 2223本文源自《编程之美》3.5 最短摘要生成一课。 ... -
K-MEDOIDS聚类算法
2012-12-04 21:18 1945k-medoids聚类算法 (wiki上讲得很清楚啊:) ) ... -
搜索(三)——回溯
2012-11-23 15:23 1026一、回溯 和 深度搜索 ... -
哈希Hash
2012-11-21 14:42 978要点一:哈希表长度 的确定是个两难的问题:太短则容 ... -
状态压缩DP
2012-11-14 20:27 730引例、 例1、 例2、 例3、 ... -
模拟退火
2012-10-28 16:34 1203引用:http://www.cnblogs.com/heaad ... -
计算几何(一)——基础算法
2012-07-12 21:07 1904待续 《计算几何资料》为提纲 1. (1) 有向线段 ... -
计算几何(二)——平面最近点对
2012-07-12 10:54 890参考资料: 为何这个问题采用分治法 http://blog ... -
气泡滚大——剔除线性数据中的杂质
2012-06-18 09:43 943这是一道Java的面试题,但是我总结了除了一种自称为“ ... -
深入理解二分查找(二、二分答案)
2012-04-29 16:24 7182二分答案 如果已知候选答案的范围[min,max ... -
P问题、NP问题和NPC问题
2012-04-25 16:36 1048这篇文章转自这里 ... -
RMQ(Range Minimum/Maximum Query)区间最值查询
2012-04-18 20:47 1546一、RMQ问题描述 和 几种解题思路 RMQ问题 (Rang ... -
后缀数组
2012-04-16 09:49 1494一、后缀数组 及其对应的名次数组 举例:S=&quo ... -
大整数运算(部分转载)
2012-04-12 21:36 1175待补充:“浮点数高精度运算” 参见这里==> ... -
单向链表相关
2012-04-10 16:42 959单向链表是微软笔试常考的,参考这里:http://www.c ... -
关键路径(AOE)
2012-04-10 08:05 1652前面这段话是引用别人的,后面代码是自己写的,有待完善: ... -
搜索(二)——双向BFS
2012-03-24 17:18 3001参考这篇文章,以下前 ...
相关推荐
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 题解 数组篇 二. 字符串 题目分类 题目编号 字符 ...