题目描述

给定一个自然数 $N$，要求把 $N$ 拆分成若干个正整数相加的形式，参与加法运算的数可以重复。

注意:
拆分方案不考虑顺序；
至少拆分成 $2$ 个数的和。
求拆分的方案数 $\mod 2147483648$ 的结果。

输入格式

一个自然数 $N$。

输出格式

输入一个整数，表示结果。

数据范围

$1≤N≤4000$

样例

输入样例：
7
输出样例：
14

算法1 dfs暴搜

C++ 代码

//请不要抄这个代码，因为会超时的！！！
#include <bits/stdc++.h>
using namespace std;
int a[10010]={1},n,ans=0;
int search(int,int);
int print(int);
int main(){
    scanf("%d",&n);
    search(n,1);
    printf("%d",ans%2147483648);
} 
int search(int s,int t){
    int i;
    for(i=a[t-1];i<=s;i++)
        if(i<n){
            a[t]=i;
            s-=i;
            if(s==0) ans++;
            else search(s,t+1);
            s+=i;
        } 
}

算法2 完全背包

算法：完全背包或 dfs ！！！（dfs 有可能会超时，建议完全背包，这里讲的也是完全背包）我们可以把背包容量看成 $n$（因为要求总和是 $n$），总共有 $n-1$ 个物品（因为必须是正整数，不包括零，所以最小的数是 $1$，那么最大的数就是 $n-1$），每件物品的价值就是数字本身。还要注意：至少有两个数相加！！！有了这个这个思路，写起代码来一个是很简单的。。。把完全背包的模板稍微改动一下即可。

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

long long MOD=2147483648; //题目要求对答案模2147483648。这里数字较大，要开 long long

int n;

long long f[4010]; //注意f可能会很多，如果开int就过不了

int main()
{
    scanf("%d",&n);

    f[0]=1; //初值化

    for(int i=1;i<n;i++) //注意最多只能到n-1
    {
        for(int j=i;j<=n;j++) //为了防止重复计算，要从i开始
            f[j]=(f[j]+f[j-i])%MOD; //f[j]代表把j分成若干个正整数相加的形式的方案数
                                    //f[j]=等于目前j的方案数加上j-i个数的方案数，由于j在不断递增，而i在本轮里不动，所以每个数都能算到
    }

    printf("%d",f[n]);

    return 0;
}

如果觉得我的题解写得不错，那就请点个赞吧！！！祝各位学神CSP-J/S2020rp++!!!