多重集组合数（动态规划）

62 阅读 0 评论 41 点赞

我是靠谱客的博主尊敬楼房，最近开发中收集的这篇文章主要介绍多重集组合数（动态规划），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

还是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-1个选j-1-ai个的情况，因此是dp[i-1][j-1-ai]
因此，最终式子为：
在这里插入图片描述
确实很难！