整数划分问题(实际是背包问题)

鸣人的分身

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 11;
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int f[N][N]={0};
        f[0][0]=1;  //当总和为0，且个数为0的情况只有1种，就是{0}
        for (int i=0;i<=n;i++)  //注意，i要从0开始，因为可能存在总和为0的情况
            for (int j=1;j<=m;j++) //分成的个数至少为1
                {
                    f[i][j]=f[i][j-1];  //当分的情况中有0的时候，就等价与在总和为i，个数为j-1的分类方法
                    if (i>=j) f[i][j]+=f[i-j][j];  //每个数都减去1，总和变成了i-1*j，个数依旧是j个
                }
        printf("%d\n",f[n][m]);
    }
    return 0;
}

整数划分模板

整数划分

 #include <iostream>
#include <cstdio>
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]<<endl;
    return 0;
}