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）