动态规划:括号生成

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

推导出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。我想这样的差距不是一点优化可以弥补的,两点也不行。。

 

Leave a Reply

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