题目描述

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

求拆分的方案数 mod 2147483648的结果。

输入格式

一个自然数N。

输出格式

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

数据范围

1≤N≤4000

输入样例：

7

输出样例：

14

完全背包问题

$O(n^2)$

把1~n-1个数看成n-1种物品。 物品可以无限用，背包容积为n，用f[i]表示和为i的方案数

至于为什么是n-1个数，大家可以手推一下7拆成的14种情况（也可以参考洛谷P2404的样例。本人比较lan）

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4
（别数了就是14行）

因此按照题意来看，题意中的“若干”是不能为1的，就是没有n=n这种，和《算法竞赛进阶指南》的题意略有区别。

代码

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long LL;
const LL base=2147483648LL;//默认数字为int类型，因此数字后要加LL
int n;
long long f[4005];

int main(){
    scanf("%d",&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])%base;
    printf("%d",f[n]);
}