括号生成（Medium）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
Related Topics
字符串
动态规划
回溯
思路分析
这道题可以使用动态规划的思想来进行实现，动态规划就是说首先确定dp数组的定义，然后找到递进关系式，再找到初始值，就可以获得所有的结果。这道题也是使用相同的思想，虽然没有使用dp数组来进行数据的记录，但是关系传递的思想是一样的。
根据动态规划的思想，我们要想知道i=n的所有情况，首先我们要知道i<n的所有情况。我们首先添加进i=n的时候新加入的一组括号“（）”，然后把剩下的n-1添加到这一对括号中。
n-1的所有情况添加方法只有如下所示：
“(” + 【i=p时所有括号的排列组合】 + “)” + 【i=q时所有括号的排列组合】
其中 p + q = n-1，且 p q 均为非负整数。
事实上，当上述 p 从 0 取到 n-1，q 从 n-1 取到 0 后，所有情况就遍历完了。
然后我们使用递归的方式来完成这个过程。
代码实现
我自己的代码有点乱，我直接贴标准答案了文章来源：https://www.toymoban.com/news/detail-798526.html
class Solution {
ArrayList[] cache = new ArrayList[100];
public List<String> generate(int n) {
if (cache[n] != null) {
return cache[n];
}
ArrayList<String> ans = new ArrayList<String>();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left: generate(c)) {
for (String right: generate(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
cache[n] = ans;
return ans;
}
public List<String> generateParenthesis(int n) {
return generate(n);
}
}
个人笔记
动态规划总结
第一步：定义记录数组的元素，规定数组元素的含义，可能是二维数组也可能是一维数组。
第二步：找出数组元素之间的递进关系式，使用历史数据来找出下一步的数据，比如dp[n] = dp[n-1]+dp[n-2]。
第三步：找到运算的初始值，从关系式可以知道，从第n个元素可以一直回推到第一个元素，所以你找到第一个元素就等于知道了所有的情况。
具体例题可以看同专栏文章：
Leetcode刷题（一）——掷骰子等于目标和的方法数（Medium）
Leetcode刷题（十三）——正则表达式匹配（Hard）文章来源地址https://www.toymoban.com/news/detail-798526.html
到了这里，关于Leetcode刷题（二十四）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
