动态规划:括号生成

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

 

2 thoughts on “动态规划:括号生成”

  1. 您好,对于您的答案我存在一些疑问,其中“每一种拆分形式的两部分dp[i]和dp[n-1-i]做排列组合,并且只给dp[i]部分加括号,可以保证我们得到所有的组合是不重复的”,这样操作是会保证不会重复,但是如何保证最后的结果是全部的,而不会落下。我想到的处理方式是对每一种拆分形式的两部分dp[i]和dp[n-1-i],都有以下三种可能(dp[i])+dp[n-1-i],dp[i]+(dp[n-1-i]),dp[i]+()+dp[n-1-i],请问对于后两种,是如何考虑的?期待您的答复

    1. 一段时间没有打理这个网站了,抱歉回复太晚,希望还能帮到你理解,
      r[i] += [‘(‘+k+’)’+l for k in r[j] for l in r[i-j-1]]
      这一行遍历了n=i-1时的所有拆分为j/n-j的有效组合方式,单看这一行的确没有覆盖所有i-1情况下加一对括号的组合。由于“”即j=0算作一个有效拆分组,如果需要覆盖所有情况,那么应该是(r[j])r[i-j-1]和r[j](r[i-j-1])。
      但是,这一行代码是在for j in range(i)下的,所以如果每次都把两种情况放入r中,那么(r[j])r[i-j-1]和下一次循环的r[j+1](r[i-j+1-1])实际上是重复的,且最后一次循环和首次是重复的。反过来说,r[j](r[i-j-1])其实已经被上一次循环的(r[j-1])r[i-j-1-1]覆盖过了

Leave a Reply

Your email address will not be published. Required fields are marked *