#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1e3 + 10, MOD = 1e9 + 7;
int n;
int f[MAX][MAX];
int main()
{
cin >> n;
for (int i = 0; i <= n; i ++) f[i][0] = 1;
// f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - i * 2] + ... + f[i - 1][j - i * s];
// f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - i * 2] + ... + f[i - 1][j - i * s];
for (int i = 1; i <= n; i ++)
for (int j = 1; 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];
return 0;
}
终极优化版本
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1e3 + 10, MOD = 1e9 + 7;
int n;
int f[MAX];
int main()
{
cin >> n;
f[0] = 1;
// f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - i * 2] + ... + f[i - 1][j - i * s];
// f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - i * 2] + ... + f[i - 1][j - i * s];
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];
return 0;
}