$\quad$一个正整数n可以表示成若干个正整数之和，形如：$n=n_1+n_2+…+n_k$，其中$n_1≥n_2≥…≥n_k,k≥1$。我们将这样的一种表示称为正整数n的一种划分。现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示总划分数量。由于答案可能很大，输出结果请对$10^9+7$取模。

数据范围

$1≤n≤1000$

输入样例:

5

输出样例：

7

样例说明：

5 = 5
5 = 4 + 1
5 = 3 + 2
5 = 3 + 1 + 1
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

思路

$\quad$把1,2,3, … n分别看做n个物体的体积，这n个物体均无使用次数限制，问恰好能装满总体积为n的背包的总方案数（完全背包问题变形）。
- 状态表示：f[i][j]表示从前面的i个物品当中选质量恰为j的重量的方法数
- 选出若干个i，f[i][j] = f[i - 1][j](选0个i) + f[i - 1][j - i](选1个i) + f[i - 1][j - 2*i](选2个i) + ...
- f[i][j - i] = f[i - 1][j - i](选1个i) + f[i - 1][j - 2*i] + ...
- 故而，f[i][j] = f[i - 1][j] + f[i][j - i]

    #include <iostream>
    using namespace std;

    const int N = 1010, MOD = 1e9 + 7;
    int f[N][N];

    int main()
    {
        int n; cin >> n;
        f[0][0] = 1;
        for(int i = 1; i <= n; i ++ ){
            for(int j = 0; j <= n; j ++ ){
                f[i][j] = f[i - 1][j];
                if(j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % MOD;
            }
        }
        cout << f[n][n] << endl;
        return 0;
    }