我必须找出有效括号的数量。括号有两种类型[] ,()。有多少种方法可以使用 X 和 Y 的数量来构造一个有效的序列[] ,()。对于这个问题，我们认为([])是无效的方式，即() can't hold []. 有没有比递归更好的解决方案。

我试图做经典问题来实现一个算法来打印 n 对括号的所有有效组合。

我发现了这个程序（效果很好）：

据我了解，我们的想法是尽可能添加左括号。对于右括号，只有当右括号的剩余数量大于左括号时，我们才会添加它。如果我们使用了所有的左右括号，我们会将新的组合添加到结果中。我们可以确定不会有任何重复的构造字符串。

对我来说，这种递归就像当我们使用一棵树并且我们进行前序遍历时：我们去一个左节点每个时间都是可能的，如果不是我们向右走，然后我们尝试向左走就在这一步之后。如果我们不能，我们“回来”并向右走，然后我们重复遍历。在我看来，这里的想法完全相同。

所以，天真地，我认为时间复杂度会像 O(log(n))、O(n.log(n)) 或类似的对数。但是，当我试图搜索时，我发现了一个叫做“加泰罗尼亚语数”的东西，我们可以用它来计算括号组合的数量......（https://anonymouscoders.wordpress.com/2015/07 /20/its-all-about-catalan/ )

您认为时间复杂度是多少？我们可以在这里应用主定理吗？

我试图做经典问题来实现一个算法来打印 n 对括号的所有有效组合。我发现了这个程序（效果很好）：

然后，当我在搜索加泰罗尼亚数字的应用程序时，我在这里发现了一个非常有趣的应用程序：https ://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics 它说：

我们可以使用加泰罗尼亚语数来形成具有 n 个上冲程和 n 个下冲程的山脉，它们都保持在原线之上。山脉的解释是山脉永远不会低于地平线

因此，我尝试重用上面的代码来实现这个问题的解决方案。我不确定，但我认为我们可以重用这段代码，因为它们似乎具有相同的“逻辑”。不幸的是，我尝试了很多方法来用“/”和“\”替换括号，但我失败了。

我试图做这样的事情：

对我来说，它们具有相同的逻辑，例如在括号中，我们添加左括号'（'每次都是可能的，但对于右括号'）'，我们仅在右括号的数量大于左括号时才添加它。我们可以在这里做同样的推理，不是吗？我们每次都可以添加 '/' 但对于 '\' 我们必须先计算 '/' 的数量...

我发现这里特别困难的是我们如何在此处插入新行以拥有所有正确的山脉？

如果可能的话，你能帮我重用这段代码吗？或者我应该从头开始另一个代码？

我研究了矩阵链乘法问题，并且理解了算法的作用。最近，我遇到了加泰罗尼亚数字，它在解决括号问题时派上了用场。在我看来，这个问题与矩阵链乘法非常相似。事实上，在 CLRS 中，他们在矩阵链乘法一章中提到了加泰罗尼亚数字。

我很好奇你能用加泰罗尼亚数字算法解决矩阵链乘法吗？我的想法是：不，你不能解决，因为加泰罗尼亚数字描述了用括号括起来的方法的数量，而原始矩阵链问题提出了一个不同的问题——具体的安排括号的方法会产生最小的成本。

我的想法正确吗？

我是 python 的新手（和一般的编程），我在课堂上被要求计算加泰罗尼亚语数字高达 10 亿，但我为它编写的程序没有按预期工作。

这就是它打印的内容

1, 1, 2, 4, 8, 24, 72, 216, 648, 1944, 5832, 17496, 52488, 157464, 472392, 1417176, 4251528, 12754584, 38263752, 114791256, 344373768, 1033121304, 3099363912, 9298091736,

正如您从我的第四次迭代开始看到的那样，我得到了错误的数字，我不明白为什么。

编辑：我使用的数学定义没有错！我知道 Wiki 有另一个定义，但这个定义没有错。Co=1，Cn+1 = (4*n+2)/(n+2)*Cn

在 Haskell 中记忆递归函数的最快方法是什么？

背景：最近我一直在解决 Haskell 中的 Project Euler 问题。许多需要对递归定义的组合或数论函数进行多次计算，例如斐波那契数。如果这些函数被记忆，性能会显着提高，也就是说，函数的结果会被缓存以备后用。

我已经看到了很多解决这个问题的方法。最优雅的似乎是这个。一种使用 Data.IntMap（或哈希表）和 State monad。这个答案中建议了一个基于树的解决方案，这样的解决方案似乎相当普遍。再举一个例子，请看这篇博文。我见过使用内置函数的其他解决方案。在第 2 节中有fix一个与. 还有几个预建的解决方案。

我想知道对于 Project Euler 中使用的各种函数，哪种记忆方法在实践中最快。我的直觉说哈希表库是，因为哈希表似乎是命令式语言中首选的字典结构。纯功能树解决方案很酷，但我的谷歌搜索告诉我，它们在渐近性能方面比哈希表差。

编辑

一些评论说这个问题太宽泛而无法回答，经过反思，我同意。因此，让我给出两个要记忆的函数的具体示例：一个递归计算第 n 个斐波那契数的函数，以及一个递归计算加泰罗尼亚数的函数。我想为大 n 多次计算这些函数。

我知道这些有明确的公式，但让我们忽略这一点，因为这里的真正意义是使用它们来对记忆技术进行基准测试。

对于 n=3 对起伏，我有 5 种可能的方式来绘制这些山脉。（我永远不应该低于 x=0 轴）。我有以下长 javascript 代码，当我在浏览器的控制台中打印这些输出时可以正常工作。但是，当我尝试将它们输出为 html 时，起伏没有正确对齐。这是我的代码：

它像这样打印它们：

有人知道我如何正确输出它们吗？

目标是生成加泰罗尼亚语数字！我的代码工作到 n = 30（我在 JAVA 中尝试了相同的算法，它完全正确，但是，python 发生了一些奇怪的事情，它在 n = 30 之后返回错误的数字。我完全确定存在问题关于舍入或格式，但我自己无法弄清楚！

我正在尝试为该算法编写递归关系。但是我对“根”变量感到困惑。谁能帮助我或建议我一个更好的递归算法来计算具有 n 个节点的可能二叉树的数量？

到目前为止我已经写了这个，但我不知道如何处理根来解决这个问题。

T(n) = n[T(root-1)+T(n-root)]

我正在尝试编写一个程序，该程序从用户那里获取一个整数值（n），检查它是否大于 0 且小于 30。如果是这种情况，它会调用我的 catalan numbers 方法并替换 n。如果输入number 小于 0 或大于 30 它应该抛出和 IllegalArgumentException。

加泰罗尼亚数字方法似乎没有问题，但是当我尝试调用加泰罗尼亚数字方法并在其中输入“n”时会出现问题。所有的问题都局限于 switch 语句，它不会接受函数 'n.equals("quit")、(n>30)、(n < 0)，它不会调用我的 catalan numbers 方法。

到目前为止，这是我的代码：

如果有人对此有任何解决方案，我将不胜感激。