计算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个人。所以，让我们谈谈Xth人，他可能想保持单身，或者他可以和某个人在1，X-1上配对。

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

我理解他保持单身的情况(f( x-1 ))，但在另一种情况下，选择其他伴侣的可能方式是x-1，但为什么要乘以f(x-2)。

Answer 1

关于另一个人想要配对的情况:在这个例子中，在选择了一个人之后，剩下的人是X-2，答案是F(X-2)。

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