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

动态规划之滚动数组

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

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

#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;
}

总结:3个数互相倒腾，就开一个3个长度的数组，然后不断取模，以此类推。

---

例题:一个楼梯有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开始).采用左边的状态转移方程。对应的求解算法如下:

#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],对应的完整程序如下:

#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;
}

其他二维数组及高维数组也可以做这样的改进。例如，一个采用普通方法实现的算法如下:

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],所以可以使用滚动数组,对应的算法如下:

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空间相同的效果。