algorithm - 计算 N 个人形成对的方式的数量

Question

这就是问题。

在代码世界中，所有性别都被认为是平等的（这意味着他们与男性或女性完全不同）。现在他们是生活在这个假设世界中的 N 个不同的人。每个人都可以与任何其他人配对，甚至可以保持单身。有一天，Vbhu 计划访问代码世界。作为一个数学家，他总是试图成为数学家。因此，他开始计算生活在代码世界中的 N 个人可以结对或保持单身的方式。一个人最多可以与另一个人配对。看到 N 可能很大，Vibhu 向您寻求帮助。现在，作为一名出色的程序员，您需要帮助 Vbhu 计算生活在代码世界中的 N 个人可以结对或保持单身的方式的数量。

问题链接=https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/vibhu-and-his-mathematics/description/

编辑解决方案：

让 F(X) 表示上述问题的方法数，这意味着我们有 X 人。所以，让我们谈谈第 X 个人，他可能想保持单身，或者他可以与 [1,X-1] 中的某个人配对。

因此，考虑这两种情况并将其添加到最终答案中，我们得到递归：- F(X) = F(X-1) + (X-1)*F(X-2)。让我们看一下实现递归方法的伪代码。

我理解他保持单身的情况（f（x-1）），但对于另一种情况，选择其他伙伴的全部可能方法是 x-1 但为什么要乘以 f（x-2）

标签： algorithmdynamic-programmingcombinatorics

Answer 1

关于该人要配对的其他情况：在这种情况下，在选择要配对的人之后，剩下的人就是X-2答案为 的人F(X-2)。

有很多X-1方法可以选择合作伙伴。对于选择合作伙伴的每个选项，都有F(X-2)方法和(X-1)选项 - 总方法是(X-1)*F(X-2)。