尊敬楼房

文章
3
资源
0
加入时间
2年10月21天

多重集组合数(动态规划)

还是dp然后我们需要对dp[i+1][j]进行拆分几种情况:1.不选第i种,也就是第i种物品选0个,那么显然这时候就是dp[i][j]2.选第i种,这时候假设我们可以选无限个,那么第i种可以选1,2,…,假如这时候对第i种选取的个数减1,那么它就可以从0一直选到正无穷,同时j个物品也将变成j-1个,这时候对应的就是dp[i+1][j-i]3.选第i种,但是第i种最多只能选ai个,那么我们在第二步减1后会发现,我们是选不到ai的(最多选到ai-1),这时候第i种对应选ai个的情况,就相当于前i-.