Leetcode刷题（二十四）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode刷题（二十四）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

括号生成（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 后，所有情况就遍历完了。
然后我们使用递归的方式来完成这个过程。

代码实现

我自己的代码有点乱，我直接贴标准答案了

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模板网！