题目描述
有 n 种物品，第 i 种物品有 a_i 个，不同种类的物品可以互相区分, 但相同种类的无法区分。从这些物品中取出 m 个, 有多少种取法? 求出数模 M 的余数.：
解析
考虑使用动态规划方法进行实现，定义状态方程为：dp[i][j]=前 i 类物品中取出 j 个的组合总数。可以得到以下状态转移方程：
以上递推公式包含三层循环，时间复杂度为 O(n*m^2)，显然是过高了，于是我们考虑进行优化：
……继续阅读 »
yanzexi
2年前 (2022-10-07) 741浏览 0评论
10个赞
