首页 > 代码库 > 滚动数组~\(≧▽≦)/~

滚动数组~\(≧▽≦)/~

今天第一次用了滚动数组,缘由要从一道题说起:POJ 1159 Palindrome

   题意:给你一个字符串,求对字符串最少添加几个字符可变为回文串。

   分析: 简单做法是直接对它和它的逆序串求最长公共子序列长度len。n-len即为所求。至于为什么,小盆友们可以自己模拟一下下。O(∩_∩)O~因为这不是我们今天讲的重点~噶呜

很明显这是一道LCS题,如果你还不知道什么是LCS,可以点击  LCS  ,我们都知道要开辟一个dp[5001][5001]的数组来存LCS值,问题来了,当我开心的交上代码的时候竟然

内存超限了~!!看了下讨论组,说改成short int 能过,果然过了,但是memory==49156.。。太大了。上网一搜,发现了滚动数组这个东西,memory立即编程188K。啥都不说了,进入正题!

    滚动数组的作用在于优化空间,主要应用在递推或动态规划中(如01背包问题)。因为DP题目是一个自底向上的扩展过程,我们常常需要用到的是连续的解,前面的解往往可以

舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

    一个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]决定,空间复杂度差别巨大。

   学以致用:http://poj.org/problem?id=1159 小盆友们快去做一做吧~噶呜~