multiset combination problem

问题描述

假设有n类物品，其中第i类物品的数量为a_i个。各类物品之间具有可区分性，而同一类别的物品则无法进行区分。若从所有这些物品中选取m个，问共有多少种不同的选取方式？
约束条件：
1、1 \le n \le 1000
2、1 \le m \le 1000
3、1 \le a_i \le 1000

样例

给定参数如下：
n=3
m=3
数组a的元素为[1,2,3]
计算结果：
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个的组合数
递推关系： 若需从前i种物品中选取j个，可考虑从前i-1个物品中选取j-k个，再从第i种物品中选取k个进行补充，因此得出：
dp[i+1][j]=\sum_{k=0}^{min(j,a_i)}dp[i][j-k]
若直接采用该递推表达式，则其时间复杂度为O(nm^2)。显然，在最坏情况下，计算次数将高达10^9次。为了优化这一过程，我们对\sum_{k=0}^{min(j,a_i)}dp[i][j-k]进行分类分析并展开处理：
1、当