动态规划（二）：括号生成
题目：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2：
输入：n = 1
输出：[“()”]
提示：
1 <= n <= 8
解：
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def gen(p, lc, rc, r, n):
if lc > n:
return
if lc == n and rc == n:
r.append(‘’.join§)
p.append(‘(’)
print(“p,lc,rc,r当前状态为”,p,lc,rc,r)
lc += 1
gen(p, lc, rc, r, n)
p.pop()
print(“p,lc,rc,r当前状态为”, p, lc, rc, r)
lc -= 1
if lc > rc:
p.append(‘)’)
print(“p,lc,rc,r当前状态为”, p, lc, rc, r)
rc += 1
gen(p, lc, rc, r, n)
p.pop()
print(“p,lc,rc,r当前状态为”, p, lc, rc, r)
rc -= 1
results = []
gen([], 0, 0, results, n)
return results
%%
s = Solution()
print(s.generateParenthesis(n = 2))
代码讲解
代码逐行解释如下：
-
from typing import List
: 这一行导入了
typing
模块中的
List
类型。它用于为函数的参数和返回值提供类型提示。在这里，它表明
generateParenthesis
方法将返回一个字符串列表。 -
class Solution:
: 这定义了一个名为
Solution
的类，包含了
generateParenthesis
方法。 -
def generateParenthesis(self, n: int) -> List[str]:
: 这是
Solution
类中
generateParenthesis
方法的定义。它接受一个整数
n
作为输入，并返回一个字符串列表（
List[str]
）。该方法将用于生成包含
n
对括号的所有合法组合。 -
def gen(p, lc, rc, r, n):
: 这是一个名为
gen
的辅助函数，用于递归地生成括号的组合。它接受以下参数：-
p
: 一个列表，表示当前正在构建的括号组合。 -
lc
: 一个整数，表示当前组合中左括号
'('
的个数。 -
rc
: 一个整数，表示当前组合中右括号
')'
的个数。 -
r
: 存储结果（合法括号组合）的列表。 -
n
: 一个整数，表示要生成的括号对数。
-
-
if lc > n: return
: 这是递归函数的基本情况。如果左括号的个数
lc
超过了
n
，则函数直接返回，因为它不是一个合法的组合。 -
if lc == n and rc == n: r.append(''.join(p))
: 这检查左括号的个数
lc
和右括号的个数
rc
是否都等于
n
。如果是，意味着我们已经形成了一个合法的括号组合，并将其添加到结果列表
r
中。 -
p.append('(')
: 向当前组合
p
中添加一个左括号
'('
。 -
lc += 1
: 增加左括号的个数
lc
。 -
gen(p, lc, rc, r, n)
: 递归调用
gen
函数，传入更新后的
p
、
lc
、
rc
、
r
和
n
的值。这将探索一个额外的左括号的组合。 -
p.pop()
: 从当前组合
p
中删除最后一个元素（即左括号
'('
）。 -
lc -= 1
: 减少左括号的个数
lc
。 -
if lc > rc:
: 检查左括号的个数
lc
是否大于右括号的个数
rc
。如果是，表示我们可以向当前组合添加一个右括号，形成一个合法的括号组合。 -
p.append(')')
: 向当前组合
p
中添加一个右括号
')'
。 -
rc += 1
: 增加右括号的个数
rc
。 -
gen(p, lc, rc, r, n)
: 递归调用
gen
函数，传入更新后的
p
、
lc
、
rc
、
r
和
n
的值。这将探索一个额外的右括号的组合。 -
p
: 最后的
p
列表是函数返回时的状态，它表示了一个合法的括号组合。所有生成的括号组合将存储在结果列表
r
中，最终函数返回
r
。
动态演示
算法思路
在这个问题中，虽然代码并没有显式使用动态规划的方法，但实际上，它使用了类似动态规划的思想来解决问题。
在动态规划中，通常会将问题分解为子问题，并通过求解子问题来得到原问题的解。这种思想在递归中得到体现。在代码中，
gen
函数就是一个递归函数，它通过不断调用自身来探索所有可能的括号组合。
具体体现动态规划思想的部分是在
gen
函数的递归过程中：
-
gen(p, lc, rc, r, n)
递归地构建括号组合，对于每个当前的状态
(p, lc, rc)
，它根据条件进行判断和分支。 -
当满足
lc == n
和
rc == n
的条件时，将当前的括号组合加入到结果列表
r
中。这表示已经找到了一个合法的括号组合。 -
在递归过程中，每次递归都会构建一个新的
p
列表，并在其中添加左括号或右括号。通过这样的方式，
gen
函数会尝试所有可能的括号组合，直到达到合法的括号组合。
虽然这个问题没有显式地使用动态规划的数组来存储子问题的解，但是通过递归过程，它仍然实现了类似动态规划的思想，将大问题拆分成更小的子问题，并通过递归的方式逐步解决子问题，最终得到原问题的解。
需要注意的是，虽然这种递归实现在小规模问题上是有效的，但对于较大的
n
值，由于存在大量的重复计算，它的时间复杂度可能较高。在实际应用中，可以进一步优化使用动态规划的方法来存储子问题的解，避免重复计算，提高效率。
做完这道题，让我觉得不能用正常的线性数据结构思维的方法来进行迭代，也就是遍历不仅限于从0到N，从0到N的遍历每个元素后只跟着一个值，一种可能性。而对于该题就适用二叉树的遍历方法，要生成所有可能性，每一个位置上要么“(”要么“)”，正好两种可能性。然后使用了lc和rc来控制位置。比如在该题目中，把它想象成一棵树，就是每次向左子树上探索，达到约束条件后退回，探索右子树。而在二叉树的遍历中，递归和回溯法是非常适用的，