小编And*_*rew的帖子

我想知道如何使用DP解决这样的问题.

给定n个球和m个箱子,每个箱子有最大值.容量c1,c2,... cm.将这些n球分配到这些m箱中的总方式是多少？

我面临的问题是

1. 如何找到一个递归关系(我可以当容量都是一个单一的常数c).
2. 将有几个测试用例,每个测试用例都有自己的c1,c2 .... cm.因此DP如何实际应用于所有这些测试用例,因为答案明确取决于当前的c1,c2 .... cm,并且我无法存储(或预先计算)c1,c2的所有组合的答案. ...厘米.

另外,我也不能为这个问题提出任何直接的组合公式,我也不认为存在这个问题.

我想知道我们可以用多少种方式将数字 x 表示为给定数字集合 {a1.a2,a3,...} 中的数字之和。每个数字可以被多次取走。

例如，如果x=4且a1=1,a2=2，则x=4的表示方式为：

1+1+1+1\n1+1+2\n1+2+1\n2+1+1\n2+2\n

因此路数=5。

我想知道是否存在一个公式或其他一些快速方法可以做到这一点。我无法用暴力破解它。我想为它编写代码。

注意：x 可以大到 10^18。a1,a2,a3,\xe2\x80\xa6 的项数最多可达 15 个，并且 a1,a2,a3,\xe2\x80\xa6 中的每一项也最多只能达到 15 个。