在高分篇中，我们学习了简单背包问题，和01背包问题。
当时我们用的二维数组来进行递推的，仔细思考就可以发现其实我们没有必要开这么大的数组。因为我们所有的递推都是从上一行推到下一行的，也就是说，我们只需要开两行的数组即可完成这个过程。我们还可以进一步压缩空间，前半段和后半段也可以进行滚动。

滚动数组（上下滚动）

#include <stdio.h>  
#include <string.h>  
  
int main() {  
    int dp[2][1005] = {0};//只需要0和1进行滚动  
    int w[1005];  
    int s, n;  
    while (scanf("%d%d", &s, &n) != EOF) {  
        for (int i = 1; i <= n; i++)  
            scanf("%d", &w[i]);  
        memset(dp, 0, sizeof(dp));  
        dp[0][0] = 1;  
        for (int i = 1; i <= n; i++) {  
            int now = i & 1;  
            for (int j = s; j >= 0; j--) {//将i-1变成i^1  
                if (dp[now^1][j] == 1) dp[now][j] = 1;  
                if (j - w[i] >= 0 && dp[now^1][j-w[i]] == 1) dp[now][j] = 1;  
            }  
        }  
        if (dp[n&1][s] == 1) printf("YES\n");  
        else printf("NO\n");  
    }  
    return 0;  
}  

滚动数组（前后滚动）

#include <stdio.h>  
#include <string.h>  
  
int main() {  
    int dp[1005] = {0};//前后滚动  
    int w[1005];  
    int s, n;  
    while (scanf("%d%d", &s, &n) != EOF) {  
        for (int i = 1; i <= n; i++)  
            scanf("%d", &w[i]);  
        memset(dp, 0, sizeof(dp));  
        dp[0] = 1;  
        for (int i = 1; i <= n; i++) {  
            for (int j = s; j >= 0; j--) {//从后往前枚举  
                if (j - w[i] >= 0 && dp[j-w[i]]...

掌握本节内容