动态规划：括号生成

LeetCode上一个中等难度的题，可以用递归，当然也可以用动态规划（这道题目的状态转移方程有点复杂，定义为中等让我感觉被鄙视了），下面先上动态规划的代码：

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        r = [[] for i in range(n+1)]
        r[0] = [""]

        for i in range(1, n+1):
            for j in range(i):
                r[i] += ['('+k+')'+l for k in r[j] for l in r[i-j-1]]

        return r[n]

推导出dp[n]需要前面所有的状态组合起来：

通俗的说得到n个括号的组合dp[n]就是把一个括号加入到dp[n-1]的每一种组合里且得到的新的括号组合要有效。如何保证加入一个括号后的新组合有效呢？只要被新加入括号括起来的部分k=dp[i]和剩余部分l=dp[n-1-i]都是有效的，换句话说我们要把dp[n-1]中的每一种组合拆分成两部分，并给其中一部分括上一个新括号。

举个例子，如果我们要得到4个括号的组合，那么需要把3个括号所有可能组合的每一种拆分成有效的两部分，拆分完后可能是0+3,1+2,2+1,3+0这四种形式（0代表空字符串，即在dp[3]的左边或右边加一个新的括号，它括住的内容是空）。需要注意的是，并不是dp[3]中的每一种组合都可以拆成这4种，比如((()))这个就只能拆成3+0和0+3。正向思维的拆分看起来是非常复杂的，因为要区别对待各种情况，此时采用反向思维，我们不去拆而是去构建，用来构建的材料则是dp数组中现成的。按照前面的4种拆分形式我们对号入座，做个排列组合就可以了。

每一种拆分形式的两部分dp[i]和dp[n-1-i]做排列组合，并且只给dp[i]部分加括号，可以保证我们得到所有的组合是不重复的。我们称i部分为“括号内”，长度为2i，n-1-i部分为“剩余部分”。我们是给括号内部分整个括上一个括号，长度变成了2i+2，不同的拆分形式之间一定不会重复，因为对i,n-1-i这种拆分，加完括号后，第2i+2和2i+3字符中间一定是可以拆分的，而i+1,n-i以及之后的所有拆分形式在2i+2和2i+3之间是绝不可能有效拆分的。举例来说：

()()() 拆分成 () | ()()和()() | ()，加完括号后变成：(()) | ()()和(()( | )) ()

同样的位置加入分隔符，一个一定是有效分割，一个一定是无效的（加括号前括号内部分也是两两成对的，总长2i，最外层加括号，只能是最外层自己配对，所以在第2i+2个字符前加入分隔符一定会破坏最外层的括号）

加括号后，不同拆分之间不会出现重复；那么同种拆分内部会不会出现重复，这个很简单，因为是排列组合，括号内部分相同的，剩余部分就不同，而剩余相同的括号内也一定不同。

总的来说，上面代码体现的状态转移方程，一定是结果有效且全覆盖的，满足了这两个条件，我们的状态转移方程就能推导出所有正确结果了。

附上递归算法，笔者没有优化递归算法的代码，递归算法执行耗费了876ms，而上述动态规划算法只花费了36ms。我想这样的差距不是一点优化可以弥补的，两点也不行。。

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        r = ["()"]
        if n == 1:
            return r

        for i in range(n-1):
            t = []
            for j in r:
                jl = list(j)
                for k in range(len(j)):
                    jl.insert(k, "(")
                    for l in range(k+1, len(jl)+1):
                        jl.insert(l,")")
                        j = ''.join(jl)
                        if j not in t:
                            t.append(j)
                        jl.pop(l)
                    jl.pop(k)
            r = t
        return r