两种不同的集合表示方法

1. 将其视为普通的完全背包问题

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int f[N];
int n;

int main()
{
    cin >> n;

    f[0] = 1;

    for(int i = 1; i <= n; i ++ )
        for(int j = i; j <= n; j ++ )
        {
            f[j] = (f[j] + f[j - i]) % MOD;
        }

    cout << f[n];
}

2.全新的状态表示 — 集合

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010, MOD = 1e9 + 7;
int f[N][N];
int n;

int main()
{
    cin >> n;
    f[1][1] = 1;
    for(int i = 2; i <= n; i ++ )
        for(int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % MOD;




    long long res = 0;
    for(int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % MOD;

    cout << res;
}