朴素完全背包求解：

参考代码：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N][N];

// 完全背包求解：
// 1，2，3 ... n 可以看成n个物品的体积，此n个物品的选择无次数限制，背包体积为n，该问题变为了从n个物品中选(可选无限次)使得背包体积恰好为n的选法

// f[i][j]：表示从前i个物品中选使得体积恰好等于j的选法
// 考虑最后一步i的选择个数
// f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i] (s * i <= j)
// f[i][j - i] =           f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i]
// 化解得：f[i][j] = f[i - 1][j] + f[i][j - i];

int main(){
    cin >> n;
    // 前0个物品不选使体积为0的选法为 1 （不选也是一种选法）f[0][j] = 0 (无法从前0个物品选使得体积为j,不选也不行)
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n; j++)
            if(j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
            else f[i][j] = f[i - 1][j] % mod;

    cout << f[n][n] << endl;
    return 0;
}

二进制优化空间版本

自认为这样写比压缩为一维更好理解

参考代码：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[2][N];

// 完全背包求解：
// 1，2，3 ... n 可以看成n个物品的体积，此n个物品的选择无次数限制，背包体积为n，该问题变为了从n个物品中选(可选无限次)使得背包体积恰好为n的选法

// f[i][j]：表示从前i个物品中选使得体积恰好等于j的选法
// 考虑最后一步i的选择个数
// f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i] (s * i <= j)
// f[i][j - i] =           f[i - 1][j - i] + f[i - 1][j - 2 * i] ... f[i - 1][j - s * i]
// 化解得：f[i][j] = f[i - 1][j] + f[i][j - i];

int main(){
    cin >> n;
    // 前0个物品不选使体积为0的选法为 1 （不选也是一种选法）f[0][j] = 0 (无法从前0个物品选使得体积为j,不选也不行)
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= n; j++)
            if(j >= i) f[i & 1][j] = (f[i - 1 & 1][j] + f[i & 1][j - i]) % mod;
            else f[i & 1][j] = f[i - 1 & 1][j] % mod;

    cout << f[n & 1][n] << endl;
    return 0;
}

一维压缩版本

参考代码：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N];

int main(){
    cin >> n;
    // 体积为0的选法为1（即都不选择）
    f[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            // f[i][j] = f[i - 1][j] + f[i][j - i];
            // 对于f[i - 1][j]：很明显就是将上一层的f[i]赋值到了本层，不需要其他处理
            // 对于j - i：j - i < j 即从前往后算j - i 一定会先算，计算的就是f[i][j - 1]的情况
            f[j] = (f[j] + f[j - i]) % mod;

    cout << f[n] << endl;
    return 0;
}

换一种思路：奇葩思路（很难想到）

转移方程也不好考虑，以及集合划分不好想

参考代码：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N][N];

// f[i][j]：表示总和为i,恰好选了j个数的方案数
// 集合分为两类：选了1 / 没选1 (奇葩思路)
// 1. 选了1，去掉一个1，f[i - 1][j - 1]
// 2. 没选1，则将j个数都减去1，f[i - j][j] (奇葩思路)

int main(){
    cin >> n;
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
    // j <= i 才会使得集合的两部分合法，不重不漏，选1和不选1
        for(int j = 1; j <= i; j++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}