C++

$\color{#cc33ff}{— > 算法基础课题解}$

解法一：完全背包

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010, M = 1e9 + 7;

int n;
int f[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]) % M;

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

解法二：

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010, M = 1e9 + 7;

int n;
int f[N][N];

int main() {
    cin >> n;

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % M;

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

    cout << res;
    return 0;
}