算法进阶指南----自然数拆分[完全背包问题转化]!

题目传送门

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

注意:

拆分方案不考虑顺序； 至少拆分成 2 个数的和。 求拆分的方案数 mod2147483648 的结果。

输入格式 一个自然数 N。

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

数据范围 1≤N≤4000

思路: dfs跑全排列肯定不行了,数据范围这么大, 所以我们仔细想想会发现这是一个背包问题 我们可以把N 看作 背包的容量 和 体积 因为我们对于所有的 1~n-1的数都可以选任意次 所以可以看作是一个完全背包问题

代码实现

#include 
using namespace std;
const int N  = 1e4+10;
typedef long long ll;
ll f[N];
int w[N],v[N];
int n,m;
const int mod =2147483648;
int main()
{
    cin>>n;
    f[0] =1 ;
    for(int i=1;i