python/TangDou/AcWing/DP/滚动数组.md

### 动态规划之滚动数组

实际上，滚动数组应用的条件是基于**递推**或**递归**的状态转移中，反复调用当前状态前的几个阶段的若干个状态，而每一次状态转移后有固定个数的状态失去作用。滚动数组便是充分利用了那些失去作用的状态的空间填补新的状态，一般采用求模($\%$)的方法来实现滚动数组。

 举个求斐波那契数列的例子吧。其中采用了一个$dp$数组，实际上可以改为只使用$dp[0]、dp[1]、dp[2]$这$3$个元素空间，采用求模来实现。对应的算法如下:

```c++
#include <bits/stdc++.h>
using namespace std;

int n;
int f[3];
int Fib() {
    f[1] = 1, f[2] = 1;
    for (int i = 3; i <= n; i++)
        f[i % 3] = f[(i - 2) % 3] + f[(i - 1) % 3];
    return f[n % 3];
}

int main() {
    scanf("%d", &n);
    printf("%d\n", Fib());
    return 0;
}
```
 <font color='red' size=3><b>总结:$3$个数互相倒腾，就开一个$3$个长度的数组，然后不断取模，以此类推。</b></font>

--- 
**例题**:一个楼梯有$n$个台阶，上楼可以一步上一个台阶，也可以一步上两个台阶，求上楼梯共有多少种不同的走法。

思路:设$f(n)$表示上$n$个台阶的楼梯的走法数。显然$f(1) = 1$,$f(2) = 2$
**一种走法是一步上一个台阶，走两步，另外一种走法是一步上两个台阶。**

对于大于$2$的$n$个台阶的楼梯，一种走法是第一步上一个台阶，剩余$n-1$个台阶的走法数是$f(n-1)$；另外一种走法是第一步上两个台阶，剩余$n-2$个台阶的走法数是$f(n-2)$,所以有$f(n)=f(n-1)+f(n-2)$。对应的状态转移方程如下:

$\large \displaystyle f(n)=
 \left\{\begin{matrix}
1 & n=1 \\ 
2 & n=2  \\
f(n-1)+f(n) & n>2
\end{matrix}\right.
\ 或者 \ 
\large \displaystyle f(n)=
\left\{\begin{matrix}
1 & n=0 \\ 
2 & n=1  \\
f(n-1)+f(n) & n>1
\end{matrix}\right.
$

---

用一维动态规划数组$dp[n]$(下标从$0$开始)存放$f(n+1)$(下标从$1$开始).采用左边的状态转移方程。对应的求解算法如下:

```c++
#include <bits/stdc++.h>
using namespace std;
//用例：
/*
20

输出：
10946
*/
const int N = 110;
int f[N];
int n;
int solve() {
    f[0] = 1, f[1] = 2;
    for (int i = 2; i < n; i++)
        f[i] = f[i - 1] + f[i - 2];
    return f[n - 1];
}
int main() {
    scanf("%d", &n);
    printf("%d\n", solve());
    return 0;
}
```
但$f[i]$只与$f[i-1]$和$f[i-2]$两个子问题解相关，共$3$个状态,所以采用滚动数组，将$f$数组设置为$f[3]$,对应的完整程序如下:

```c++
#include <bits/stdc++.h>

using namespace std;
//用例：
/*
20

输出：
10946
*/
int f[3];
int n;
int solve() {
    f[0] = 1, f[1] = 2;
    for (int i = 2; i < n; i++)
        f[i % 3] = f[(i - 1) % 3] + f[(i - 2) % 3];
    return f[(n - 1) % 3];
}
int main() {
    scanf("%d", &n);
    printf("%d\n", solve());
    return 0;
}
```

其他二维数组及高维数组也可以做这样的改进。例如，一个采用普通方法实现的算法如下:
```c++
void solve(){
    int f[N][N];
    memset(f,0,sizeof(f));
    for(int i = 1;i < N;i++)
        for(int j = 1;j < N;j++)
            f[i][j] = f[i - 1][j] + f[i][j - 1];
}
```

若$N$为$1000$，上面的方案需要$1000 * 1000$的空间,而$f[i][j]$只依赖于$f[i-1][j]$和$f[i][j-1]$,所以可以使用滚动数组,对应的算法如下:

```c++
void solve(){
    int f[2][N];
    memset(f,0,sizeof(f));
    for(int i = 1;i < N;i++)
        for(int j = 0;j < N;j++)
            f[i % 2][j] = f[(i - 1) % 2] + f[i % 2][j - 1];
}
```
改用滚动数组后仅仅使用了$2 * 1000$的空间就获得$1000 * 1000$空间相同的效果。