动态规划之滚动数组

动态规划之滚动数组

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

举个求斐波那契数列的例子吧。其中采用了一个\(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\)空间相同的效果。