博客

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

注意点

1、动态规划类似与数学中的数学归纳法，知道i = n – 1；推导i = n；

2、已知i = 0 时，dp[0]为[]；

3、当i = 1时，组合一定以“(”开头，以“)”结束，”(” + dp[0] + “)” + dp[0] = ()，所以dp[1] 为 [“()”];

4、当i = 2时，组合一定以“(”开头，以“)”结束，”(” + dp[0] + “)” + dp[1]= ()()，”(” + dp[1] + “)” + dp[0] = (())，所以dp[2]为[“()()”,”(())”];

5、当i = n时，组合一定以“(”开头，只需要确定“)”结束的位置，并且”(“、”)”之间的括号组合必须为合法的（dp[a]），然后只需要将剩下的n – 1 – j个括号组合放在右侧即可（dp[b]），所以可以推导出dp[n] = “(” + dp[a] + “)” + dp[b]；（a = 0 ~ i-1，a + b = n – 1）。

实现

    public List<String> generateParenthesis(int n) {
        if(n == 0) return new ArrayList<String>();
		
		//初始化dp，将dp[0]设置为[]
        List<List<String>> dp = new ArrayList<>();
        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp.add(dp0);
		
		//根据dp[0]，依次计算出dp[1]、dp[2]...dp[n]
        for(int i = 1; i <= n; i++){
            List<String> temp = new ArrayList<>();
            for(int j = 0; j < i; j++){
            	 //i = j时所有括号的排列组合
                 List<String> a = dp.get(j);
                 //剩下所有括号的排列组合
                 List<String> b = dp.get(i - j - 1);
                 for(String str1: a){
                     for(String str2 : b){
                     	 //计算所有的排列组合
                         temp.add("(" + str1 + ")" + str2);
                     }
                 }
            }
            dp.add(temp);
        }    
        return dp.get(n);
    }