一个正整数 \(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

解法一：完全背包问题

分析：

这个问题可以看成一个完全背包问题，背包的容积是这个数 \(n\) ，每一件物品是数字 \(1\) ~ \(n\) 中的一个数，价值和体积也就是这个数字本身的大小，每一件物品可以选无限次。

要计算的是恰好能把体积为 \(n\) 的背包装满的总方案数。

初始化：
求最大价值，当都不选时，价值显然是 \(0\)

而求方案数时，当都不选时，方案数是 \(1\)（即前 \(i\) 个物品都不选的情况也是一种方案），所以需要初始化为 \(1\)

即：for (int i = 0; i <= n; i ++) f[i][0] = 1;

当然，\(i>=1\) 的状态都可以从 \(i=0\) 转移过去，可以直接写 f[0][0] = 1。

压缩到一维后： f[0] = 1

状态计算：

\(f[i][j]\) 表示前 \(i\) 个整数\(（1,2…,i）\)恰好拼成 \(j\) 的方案数
求方案数：把集合选 \(0\) 个 \(i\) ， \(1\) 个 \(i\) ， \(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;
    
    for (int i=0;i<=n;i++) f[i][0] = 1;
    
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=n;j++)
        {
            if (j < i) f[i][j] = f[i-1][j] % mod;
            else f[i][j] = (f[i-1][j] + f[i][j-i]) % mod;
        }
    }
    cout <<f[n][n];
}

一维：

#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9+7;
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]) % mod;
        }
    }
    cout <<f[n];
}S

解法二

状态表示：

\(f[i][j]\) 表示总和为 \(i\) ，并且恰好表示成 \(j\) 个数的和的方案数。

状态计算：

分成两部分：

1. 最小值是 \(1\) ：
   去掉一个 \(1\) ，即是 \(f[i-1][j-1]\) 的方案数、
2. 最小值大于 \(1\) ：
   让所有数减 \(1\) ，即是 \(f[i-j][j]\) 的方案数。

所以 f[i][j] = f[i-1][j-1] + f[i-j][j]

初始化：

f[0][0] = 1 表示总和为 \(0\) 的时候的方案数是 \(1\) ，即什么都不选。

#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=1;j<=n;j++)
        {
            if (i >= j) f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
        }
    }
    int sum = 0;
    for (int i=0;i<=n;i++) sum = (sum + f[n][i]) % mod;
    cout <<sum;
}