输入:
n=3
m=3
a={1,2,3}
M=10000
输出:
6 (0+0+3,0+1+2,0+2+1,1+0+2,1+1+1,1+2+0)
为了不重复计数,同一种类的物品最好一次性处理好.于是我们按照如下方式进行定义.
dp[i+1][j]=从前i种物品中取出j个的组合总数
复杂度:O(nm)
int n,m;
int a[MAX]; int dp[MAX][MAX]; //数组 void solve()
{
//一个都不取的方法总是只有一种
for(int i=; i<=n; i++){
dp[i][]=;
}
for(int i=; i<=n; i++){
for(int j=; j<=m; j++){
if(j--a[i]>=){
//在有取余的情况下,要避免减法运算的结果出现负数
dp[i+][j]=(dp[i+][j-]+dp[i][j]-dp[i][j--a[i]]+M)%M;
}
else{
dp[i+][j]=(dp[i+][j-]+dp[i][j])%M;
}
}
}
printf("%d\n",dp[n][m]);
}