6

Leetcode上的标准Generate Parenthesis问题如下

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

在解决方案选项卡中，他们解释了我发现很难理解的闭包编号方法。

我对代码进行了试运行，甚至得到了正确的答案，但似乎无法理解它为什么起作用？这种方法背后的直觉是什么？

任何帮助将不胜感激！

4

2 回答 2

5

该算法的基本思想是动态规划。所以你试着把你的问题分解成更容易解决的小问题。在此示例中，您使子问题变得非常小，以至于解决方案是空字符串（如果大小为 0）或解决方案是“（）”（对于大小 1）。

你开始使用这样的知识，如果你想要给定长度的括号，那么第一个字符需要是 "(" 并且在字符串的稍后位置需要这个字符： ")"。否则输出无效。

现在您不知道右括号的位置，因此您只需尝试每个位置（第一个 for 循环）。

您知道的第二件事是，在左括号和右括号之间以及在右括号之后必须有一些东西，您并不真正知道它的外观（因为有很多可能性），但它必须是再次有效的括号对。

现在这个问题只是你已经解决的问题。因此，您只需输入有效括号的所有可能性（使用较小的输入大小）。因为这正是您的算法已经完成的，所以您可以使用递归函数调用来执行此操作。

总结如下：您知道问题的一部分，而其余的问题只是规模较小的同一个问题。所以你解决了你知道的问题的一小部分，然后递归地调用相同的方法来解决剩下的问题。之后，您只需将它们放在一起并获得解决方案。

动态编程通常不是那么容易理解但非常强大。因此，如果您不直接了解它，请不要担心。解决此类难题是学习动态编程的最佳方式。

于 2019-06-06T10:52:42.297 回答
1

一个序列的闭包数，其大小为序列的最小前缀，它本身就是一个有效的序列。如果一个序列的闭包数为 k，那么您知道在索引 0 中有 '(' 并且在索引 k 中有 ')' 该方法通过检查此类前缀的所有可能大小来解决问题，对于每个它都会中断序列到前缀（删除 0 和 k 元素）和序列的所有其余部分并递归解决两个子问题。

于 2019-06-06T10:53:25.517 回答