4

我正在尝试解决一个动态编程问题，部分问题涉及找到一组“p”数字的排列数，这些数字总和为一个数字“n”。p 个数集合中的每个数应介于 0 到 n 之间。

例如，如果 n = 4 和 p = 3，我有以下 12 个排列

{4,0,0},{0,4,0},{0,0,4}
{2,2,0},{2,0,2},{0,2,2}
{1,3,0},{1,0,3},{0,1,3}
{1,1,2},{1,2,1},{2,1,1}

我从这种 DP 方法开始。

n(i,j) represents number of ways of representing n using i,j in p positions

我的基本情况是

n(i,0) = n(0,i) = p

（例如，p=3 处的 n(4,0) 为 3，即 {4,0,0},{0,4,0},0,0,4}

递归案例

n(i,j) = n(i,j-1)*n(i-1,j)

（例如：n(1,2) = n(1,1) * n(0,2) 递归到 n(1,0) * n(0,1) * 2)

我不确定我是否朝着正确的方向前进，因为上述方法并没有让我得到正确的答案。请指导我正确的方向。

4

1 回答 1

7

与我的评论相反，如果我们同时计算集合的数量和这些集合的排列，这个问题实际上更容易解决。

如果我们只需要计算而不是实际生成每个集合，我们可以直接使用一些简单的组合来完成。让我们修复p = 3, n = 5我们的示例并假设我们有n = 5球：

o o o o o

现在的问题相当于，我们可以有多少种方法将球分成几组3，每组可以有[0, 5]球？想象一下，如果我们有p - 1 = 2可以单独放置在任何地方的棍子：所有五个球之前，所有五个球之后，以及任何两个球之间。例如：

| o o | o o o => (0, 2, 3)
o | | o o o o => (1, 0, 4)
o o o o | | o => (4, 0, 1)

注意问题是如何等价的？不管怎样，我们可以放那些棍子，我们也可以把我们的n球分成几p组。请注意，我们只需要p - 1棍子来生成p数字（第一根棍子之前的所有球都是第一组，最后一根棍子之后的所有球都是最后一组，两根棍子之间的任何球都是其他组）。

所以现在我们的问题是我可以用多少种方式排列我的n球和p - 1棍子？你可以把它想象成有n + (p - 1)插槽，你只是在挑选n球的位置……剩下的就是棍子所在的地方。以这种方式思考它，我们可以应用组合数学的基本公式（它已使用和的公理化规则和乘积规则得到证明......我什至不确定我是否见过证明）：

(n + (p - 1)) Choose n = (n + (p - 1))! / n! / (p - 1)!

所以在我们的例子中，它是7! / 5! / 2! = 21. 您可以在您的示例中看到它是6! / 4! / 2! = 15. 您错过了一些排列（例如，{0, 3, 1}）。

你也可以通过一个简单的递归方程用 DP 来解决这个问题。基本上

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)`

并记住 的一些值f。这个想法是，您选择集合的第一个成员的值S，然后下一个递归调用选择下一个成员，S依此类推。基本案例可能类似于f(0, p) = 1and f(n, 0) = 0，否则您可以使用递归案例。如果您实际上并不需要这些集合本身，那么封闭形式显然会表现得更好。

于 2013-06-29T01:30:39.580 回答