滚动数组详解

( 宇宙免责任书：我用的是C++)

何为滚动数组？

什么是滚动数组？是会唱跳rap的数组吗？其实滚动数组就是它名字的意思，一直在滚动的数组。更形容的说就像一个滚轮，在一个状态轴向前后滚动。那么滚轮大家都知道，它是一个动态的东西，那么放到代码中，那其实就是一个数组，像一个滚轮一样，不断的向前递进，但是递进的过程中，并不关心我们的状态，只注重结果，换句话说，这个数组只保存结果。
当然，滚动数组只是一种优化手段，通常用来优化我们的DP的空间，偶尔下降点时间复杂度。

滚动数组是如何优化空间的？

上文中提到，滚动数组其实就是一个在动态滚动的数组，它会在滚动的时候，将浪费也就是可以省的空间给省下来。举个例子，$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]]+a[i]$，我们发现，$dp[i][]$只与$dp[i-1][]$有关，与前面$dp[i-2][],dp[i-3][]...$无关，所以滚动数组就可以将它们这些空间省下来。
那么滚动数组该如何操作呢？
可以分为两种交替滚动和自我滚动。

交替滚动

顾名思义，就是两行数组交替的进行滚动:$dp[2][i]，dp[0][i]和dp[1][i]互相转移$。这种方法的有点是简单，特别简单，只要你学过数组你就会，而且代码十分明了，不容易出错。
那么操作代码该如何写呢？给出一个伪代码：

for (日常枚举)
{交换数组 开始转移 
}

如上代码是不是看起来十分简单？那么对于交换数组有两种方法，第一异或，第二直接swap。
好，现在你已经会交替滚动了。
来个例题！！！

例题：来自某某轮廓线DP的题目

题目:HDU-4064
题解：
那么好的，这是一道轮廓线DP的题目，但是我们今天的主题不是轮廓线，而是滚动数组，所以等到下次轮廓线DP的时候再重点说说吧。
先说本题主要做法吧，当然是我们的轮廓线DP,但是在做的时候如果普通的做空间直飙1e8，真的是太难受了。于是我们就要开始优化了。首先用上交 ~ 替 ~ 滚 ~ 动 ~的优化。

那么我们可以这么优化，用异或，高级点叫奇偶转变，（swap的一边去）
异或就是我们的异或符号 ^，
那么我们知道异或是不同为1，相同为0，所以拿一个数去异或1，如果是偶数，秒变奇数；如果是奇数秒变偶数。这是因为奇数末尾肯定为1，偶数末尾肯定为0，那么再异或1，就改变奇偶性了。
操作就是如下：

int cur = 0;
cur ^= 1  //变 1就是变奇数了
cur ^= 1 //变 0就是变偶数了

那么总代码就是可以写成如下样子（热心肠的我把轮廓线的部分也给加上去了）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define m_p(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define fir first
#define sec second
const int eps = 1e-8;
ll POW(int a, int b)
{ll sum = 1;for (int i = 1; i <= b; ++i) sum *= a;return sum;
}
inline int read()
{int X=0; bool flag=1; char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}if(flag) return X;return ~(X-1);
}
inline void write(ll X)
{if(X<0) {X=~(X-1); putchar('-');}if(X>9) write(X/10);putchar(X%10+'0');
}
const int mod = 1e9 + 7;
int n, m;
string MP[15][15];
ll dp[2][(1 << 20)], P;
int cur;
int check(char a)
{if (a == 'C') return 0;if (a == 'R') return 1;return 2;
}
void dfs(int pos, int now_mask, int last_mask, ll sum, char left, int hang)
{if (pos == m + 1){sum = (sum * dp[cur ^ 1][last_mask]) % mod;dp[cur][now_mask] = (dp[cur][now_mask] + sum) % mod;return ; }int tot = 0;int num[10];char one[10], two[10], three[10];for (int i = 0; i < 4; ++i){if (pos != 1 && MP[hang][pos][i] != left) continue;char right = MP[hang][pos][(i + 2) % 4];char up = MP[hang][pos][(i + 1) % 4];char down = MP[hang][pos][(i + 3) % 4];int flag = 1;for (int j = 1; j <= tot; ++j){if(right == one[j] && up == two[j] && down == three[j]){flag = 0;++num[j];break;}}if (flag){one[++tot] = right;two[tot] = up;three[tot] = down;num[tot] = 1;}}for (int i = 1; i <= tot; ++i){int jlast_mask = (last_mask * 3 + check(two[i]));int jnow_mask = (now_mask * 3 + check(three[i]));dfs(pos + 1, jnow_mask, jlast_mask, (sum * num[i]) % mod, one[i], hang);}
}
int main(){n = read(), m = read();for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> MP[i][j];P = POW(3, m);for (int i = 0; i < P; ++i) dp[0][i] = 1;cur = 0;for (int i = 1; i <= n; ++i){cur ^= 1;  //开始交替mem(dp[cur], 0);dfs(1, 0, 0, 1LL, 'z', i);}ll ans = 0;for (int mask = 0; mask < P; ++mask) ans = (ans + dp[cur][mask]) % mod;write(ans); return 0;
}

自我滚动(不如交替

你已经会交替滚动了，开始上难度了----自我滚动
我们发现，其实我们把二维转换为两个一维（反正就0/1，算成俩一维吧）。
但是实际上海能进行优化。
就继续拿上面的$dp[i][j]=max(...)$接着举例吧。
我们是可以接着优化。
我们发现它可以优化成一维，只需要自己跟以前的自己转移就行了。
但是，注 ~ 意 ~ ！！！,若上述的转移在枚举j时，一定要反过来枚举，不然可能错，因为它的结果是由同一个空间得到的，可能会影响答案正确性。

那么给出上述那个转移的代码吧（指dp[i][j] = max（…）那个）

for (int i = 1; i <= n; ++i)
{for (int j = m; j >= 1; --j){dp[j] = max(dp[j], dp[j - 1] + a[i]);}
}

完结！！！

恭喜你已经学会滚动数组了！！！
[撒花✿✿ヽ(°▽°)ノ✿]