一道简单的背包问题 P10955
大致题意：给定一个数，求可以拆分成至少两个正整数数的和的总数（数字可以无限用）
问题分析：很明显是dp，仔细思考，由于数字可以无限使用，并且目标总和不变，那么，这大概是一个完全背包了
我们令，f[j]为求数字i的方案总数，考虑转移方程，f[j] = f[j] + f[j – i]
为什么是这样的呢?
假设我们处理完了数字1 ~ i- 1，现在要加入i,那么对于任意总和j，j的方案数可以用i，也可以不用，
如果用i,那么剩下的就是 j – i,如果不用，那么还是旧的j ,二者相加，就得到了上述方程
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N = 4e3 + 10;
const int M = 2147483648;
int n;
int f[N];
signed main()
{
cin>>n;
f[0] = 1;
for(int i= 1;i <=n ;i ++)
{
for(int j = 1;j <= i; j ++)
f[i] = (f[i] + f[i – j]) % M;
}
f[n] —;
cout<<f[n]<<endl;
return 0;
}
以上为一维的做法，那么二维的该如何做呢？
二维那就更容易了，设
f
[
i
]
[
j
]
f[i][j]
f[i][j]为用前i种数字求j的总数，
显然，转移方程如下 ：
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
+
f
[
i
]
[
j
−
i
]
f[i][j] = f[i – 1][j] + f[i][j – i]
f[i][j]=f[i−1][j]+f[i][j−i] (j >= i),
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
f[i][j] = f[i -1][j]
f[i][j]=f[i−1][j] (j < i)
代码不再赘述
