博客

问题举例

有n种物品, 第i种物品有a个. 不同种类的物品可以互相区分, 
但相同种类的无法区分.
从这些物品中取出m个, 有多少种取法? 求出数模M的余数.
例如: 有n=3种物品, 每种a={1,2,3}个, 取出m=3个, 
取法result=6(0+0+3, 0+1+2, 0+2+1, 1+0+2, 1+1+1, 1+2+0).

分析

考虑动态规划的办法，设d[i][j]为取第i种数长度为j，共有多少种取法，很容易想到的是d[i][j] = sum(dp[i – 1][j – k])(k : 0 ➡ min(j,m[i]))，即对第i种数分别取长度为0到min(j,m[i])求和，为d[i][j],但是这种方法的复杂度略高，为O（n * m * m）

改进

贴上我的手推过程(✿◡‿◡)

结论

根据上述推导，可以总结出以下结论：

伪代码

for i : 1 ➡ n
	for j : 1 ➡ m
		if(j < a[i)
			①//结论中的上式
		else
			②//结论中的下式