1、题目
输入数字n，输出n对括号的可能组合。
"""
示例1：
输入：3
输出:()()(),()(()),(())(),((()))
"""
2、代码
def generateParenthesis(n):
"""动态规划，状态转移
(1)对于长度为i的括号组合，我们可以通过在长度为j的括号组合中插入新的括号来生成。
(2)遍历长度为1到n的所有括号组合，然后在每个长度为i的括号组合中，遍历长度为j的括号组合，并在每个位置插入新的括号。
(3)插入方法是:遍历以前的所有组合(0,i-1)，组合位置j(j为0到i-1)与 i-j-1 状态(因为这两个位置加和为i-1，再加上一个括号，即为i个括号)。
(4)将新生成的括号组合添加到长度为i的括号组合列表中。
返回结果：返回长度为n的所有合法的括号组合，即为 dp[n]。
"""
if n == 0: # n为0，则直接返回一个包含空字符串的列表，表示长度为0的括号组合只有一个空字符串。
return ['']
dp = [[] for _ in range(n + 1)] # 创建一个二维数组 dp，dp[i] 表示长度为i的所有合法的括号组合
dp[0].append('') # 初始化长度为0的括号组合为一个包含空字符串的列表，表示长度为0的括号组合只有一个空字符串
for i in range(1, n + 1): # 遍历长度为1到n的所有括号组合
for j in range(i): # 在生成长度为i的括号组合时，遍历长度为j的括号组合，其中j的取值范围为0到i-1
for x in dp[j]: # 遍历第j个位置的括号
for y in dp[i - j - 1]: # 对于长度为i-j-1的括号组合中的每个字符串y
dp[i].append('(' + x + ')' + y) # 插入左右括号，并与第i-j-1位置的括号组合
print(f"i:{i},dp[i]:{dp[i]}")
return dp[n]
