AcWing 900. 整数划分

//不考虑数字的顺序
//可以看出完全背包问题，1~ n-1 的数字可以用无限次
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 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]) % mod;

    cout << f[n] << endl;
    return 0;
}
//f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + …; 
//f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - 2 * i] + …; 
//因此f[i][j] = f[i - 1][j] + f[i][j - i]; 
//f[i][j]表示只从1~i中选，且总和等于j的方案数