一个正整数 nn 可以表示成若干个正整数之和，形如：n=n1+n2+…+nkn=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数 nn 的一种划分。

现在给定一个正整数 nn，请你求出 nn 共有多少种不同的划分方法。

输入格式

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

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 109+7109+7 取模。

数据范围

1≤n≤10001≤n≤1000

输入样例:

5

输出样例：

7
这个题考虑一下转化为背包问题，就是一个容量有n的一个背包，有1，2，3...n的那么多物品，通过组合恰好装满这容量为n的背包
因为一个物品（也就是一个数可以用无限多次，比如5=1+1+1+2....），所以可以看成一个完全背包
因为不考虑顺序，比如2+1+1和1+2=1是一样的，所以选什么选几个都只能对应那一种划分的形式，怎么选的方法数其实就等于有多少种划分方法
之前背包问题写的真的是罗里吧嗦的，搞得我现在回头复习思路不一样（学的多了就有自己的一个习惯了，和起初不太一样）
那现在重新说一下现在的思路：
首先就是看看最后一个状态+过程的分类+状态转移式
令f[i][j]为从1到i种选总体积恰好是j的选法的方案数
最后一个状态：到达背包容量为j的时候，第i个物品选还是不选或者说选几个（这就要看具体的背包了）
完全背包：
我看到最高赞的推导很赞

这个一看就懂hhh
(背包的推导我好像之前刚学的时候领悟不太好，这两天抽时间二刷吧...)

#include<iostream>
using namespace std;
const int N=1e3+7,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][j-i]+f[i-1][j])%mod;
        }
    }
    cout<<f[n][n]<<endl;
    return 0;
}
/*
f[i][j]=f[i-1][j]+[i-1][j-i]+[i-1][j-i*2]...
f[i][j-i]=f[i-1][j-i]+f[i-1][j-2*i]...
f[i][j]=f[i][j-i]+f[i-1][j]


*/

#include<iostream>
using namespace std;
const int N=1e3+10,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]<<endl;
    return 0;
} 

一个二维一个一维的做法

（个人喜欢二维）

另外一种方法：

令f[i][j]为总和是i，恰好表示成j个数的和的方案数

这个描述有些困难hhh，直接上图片好了（越来越水）

 

 

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    cin >> n;

    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;

    cout << res << endl;

    return 0;
}