题目描述
blablabla
样例
//推导如下
// f[i][j] = f[i-1][j] + f[i-1][j-i*1] + f[i-1][j-2*i] + f[i-1][j-3*i] + ... + f[i-1][j-s*i];可以试着这么理解,每个数都可以由几个1
//组成,1最多的状态就是j-s*i,之后1逐渐少,才开始出现2以及其他更大的数.
//f[i][j-i] = f[i-1][j-i*1] + f[i-1][j-2*i] + f[i-1][j-3*i] + ... + f[i-1][j-s*i];
//两个式子带入化简得:f[i][j] = f[i-1][j] + f[i][j-i]; 由完全背包的知识可以为:f[j]=f[j] + f[j-i];
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010,p = 1e9 + 7;
int n;
int f[N];
int main()
{
int n; 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]) % p;//因为没有溢出,所以可以省去,而不写成写为:f[i][j] = (f[i-1][j] + f[i][j-i]) % p
cout << f[n] << endl;
return 0;
}