整数划分类似于背包问题,比作从中选数就可以了
#include<iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N]; // f[i][j]表示从1~i中选 和为j的方案数
int main() {
int n;
cin >> n;
for(int i = 0; i <= n;i++) f[i][0] = 1; // 初始化
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] << endl;
return 0;
}