有 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]
我之前做过个题比较类似。