又一道不知道在哪里提交的题目。 此题为计数类DP，题为书《挑战程序设计竞赛》中的题目。（但感觉上就是一个多重背包问题，但从中学到了多重背包优化的又一个细节，看优化部分以及最后一段）。
如果有人知道在哪可以提交的话，还望能告诉我一下，谢谢啦。
题目：多重集组合数
题目
有n种物品, 第i种物品有a个. 不同种类的物品可以互相区分, 但相同种类的无法区分.
从这些物品中取出m个, 有多少种取法? 求出数模M的余数.
例如: n == 3 , m == 3 , a[1] = 1 , a[2] = 2 , a[3] = 3;
则答案为6
分别为：(0+0+3, 0+1+2, 0+2+1, 1+0+2, 1+1+1, 1+2+0)
数据范围
1000 >= n >= 1
1000 >= m >= 1
1000 >= a >= 1
f[i][j] 状态表示：前i个物品中选择总数为j的方案的总数
状态计算（暴力）：
使用类似于多重背包的方式进行求解：
a[i]要0个 : f[i - 1][j];
a[i]要1个 ：f[i - 1][j - 1];
a[i]要2个 ：f[i - 1][j - 2];
...
a[i]要s[i]个：f[i - 1][j - s[i]];
的所有情况的总和构成f[i][j]的值;
暴力算法的时间复杂度： O(nmk)
结果为1e9会TLE
暴力方式代码实现：
# include <iostream>
using namespace std;
const int N = 1010, M = 1010;
int s[N];
int f[N][M];
int n,m;
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d",&s[i]);
}
f[0][0] = 1; // 从前0个里选出对应的0个数
for(int i = 1 ; i <= n ; i++)
{
for(int j = 0 ; j <= m ; j++)
{
f[i][j] = f[i - 1][j];
for(int k = 1 ; k <= s[i] && k <= j ; k++)
{
f[i][j] += f[i - 1][j - k];
}
}
}
printf("%d\n",f[n][m]);
return 0;
}
暴力与优化的分割线
所以需要对状态计算进行优化
由于f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + … + f[i - 1][max( 0, j - s[i])];
分为两种情况:
(1)当j <= s[i]的时候，则f[i][j] = f[i - 1][j] + f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + … + f[i - 1][0];
于是我们将f[i - 1][j]先提出。 则就有f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + … + f[i - 1][0];
当j <= s[i]时
f[i][j - 1] == f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + ... + f[i - 1][0] 与上面的相同
（1）推出的结论公式：所以当j <= s[i]时，f[i][j] = f[i - 1][j] + f[i][j - 1]; //这个的优化方式感觉上 与 完全背包的优化第三层for(k)的方式很相似
(2)而当 j > s[i]时，f[i][j] == f[i - 1][j] + f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + … + f[i - 1][ j - s[i] ];
于是我们将f[i - 1][j]先提出。则就有f[i - 1][j - 1] + f[i - 1][j - 2] + f[i - 1][j - 3] + … + f[i - 1][ j - s[i] ];
当j > s[i]时
f[i][j - 1] == f[i - 1][j - 1] + f[i - 1][j - 1 - 1] + ... + f[i - 1][j - 1 - (s[i] - 1) ] + f[i - 1][j - 1 - s[i]] == f[i - 1][j - 1] + f[i - 1][j - 2] + ... + f[i - 1][j - s[i]] + f[i - 1][j - 1 - s[i]];
所以我们可以知道提出f[i - 1][j]后的公式就是f[i][j - 1] - f[i - 1][j - 1 - s[i]]
(2)推出的结论公式：所以f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1 - s[i]];
代码实现：
# include <iostream>
using namespace std;
const int N = 1010, M = 1010;
int s[N];
int f[N][M];
int n,m;
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d",&s[i]);
}
f[0][0] = 1; // 从前0个里选出对应的0个数
for(int i = 1 ; i <= n ; i++)
{
for(int j = 0 ; j <= m ; j++)
{
if(j <= s[i])
{
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
else
{
f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1 - s[i]];
}
}
}
printf("%d\n",f[n][m]);
return 0;
}
下面为：自己的某些不知道对错的感悟：
而在暴力的解法的时候我们感觉到了。似乎这就是个求多重背包的问题。
多重背包各个方式的复杂度分析：
朴素的多重背包解法为：O(nmk)
二进制优化：O(n m logk)
单调队列优化:O（nm）
那么为什么不用二进制优化啥的呢？
于是重新准备学习多重背包问题2的视频讲解的时候，里面讲了这么一个内容
将多重背包问题和完全背包问题比较，看是否可以用完全背包问题优化方式来优化多重背包问题
里面求的是max
f[i][j] = max(f[i - 1][j] , f[i - 1][j - v] + w , f[i - 1][j - 2 * v] + 2 * w ... , f[i - 1][j - k * v] + k * w;
f[i][j - v] = max(f[i - 1][j - v] , f[i - 1][j - 2 * v] + w , f[i - 1][j - 3 * v] , f[i - 1][j - k * v] + k , f[i - 1][j - (k + 1)v] + (k + 1) * v );
里面说了这么一句话。如果求的是方案数的话，我们可以直接用f[i][j - v]减去最后多出来的那一项再 + w
而我们求的是max（），这个是求不出来的，因为max不能做减法，但是如果是方案数则可以做减法。（而这个减法我一想，似乎我们上面的方法就是这个求f[i][j]用f[i][j - 1]用减法 减去最后一个多的）
于是，猜测：
计数类dp是不是就是f[][]的状态表示和计数（总数）有关，所以叫计数类dp.此题实际上就是一个多重背包问题而已。只是状态表示是要表示为恰好为j时的方案总数。
