多重集组合数

有 n 种物品，第 i 种物品有 a_i 个。不同种类的物品可以相互区分但是相同的种类无法区分。从这些物品中取出 m 个的话，有多少种取法？

感觉很简单啦，直接就能划分状态和状态转移了

f[i][j] 表示前 i 个物品，使用了 j 个有多少种取法，显然
f[i][j] = sum(f[i-1][j - k]) k =0 .. a_i
因为第 i 个物品可以取 01.. a_i 个

所以就做完了哦！
但是复杂度似乎有点高，这里有个常见的优化

我们求 f[i][j+1] 的时候可以使用 f[i][j] 计算过的值，避免重复枚举 k.
因为 f[i][j+1] = f[i-1][j+1] + ... + f[i-1][j-a_i+1]
       f[i][j] = f[i-1][j] + ...  + f[i-1][j-a_i]
所以 f[i][j+1] = f[i][j] - f[i-1][j-a_i+1] + f[i-1][j]

我之前做过个题比较类似。