hiho一下第250周《Parentheses Sequence》题目分析

3
0

这道题是一道比较复杂的动态规划题目。

首先对于任意一个括号序列S,我们都可以把S分成左右两部分,其中左边需要加若干个左括号匹配,右边需要加若干个右括号匹配。

例如S=)())(() 可以分成SL = )()) 和 SR = (()。其中SL只需要加左括号,SR只需要加右括号。

并且SL和SR是两个独立的问题,所以假设SL最少需要添加CL个括号才能匹配,并且有ANSL种最终结果;SR最少需要CR个括号才能匹配,并且有ANSR种最终结果。那么S的答案就是最少需要添加CL+CR个括号,有ANSL * ANSR种结果。

而且SL和SR本质上是一类问题。我们只需要将SL前后翻转,并且左括号/右括号呼唤,就变成了一个右半部分的问题。

例如SL = )()) 转化后变成 (()( ,对于(()(加右括号等价于对SL加左括号,所以我们只需考虑对SR加右括号这一问题即可。

假设SR = (()(()

首先最少需要添加右括号的数目可以通过栈来求出。方法是从左向右扫描每个字符,令一个变量初始等于0,遇到(加1,遇到)减1。最后变量的值就是需要添加的右括号数目。对于SR = (()(() 可以最少需要添加2个右括号。

然后我们需要解决的问题是,在不同的位置插入右括号,可能导致相同的结果。例如在SR第2个字符(从1开始)和第3个字符之后插入一个右括号,得到的字符串都是(())(()。

解决的方法是我们只允许在某个(除第一个之外)的左括号之前和SR末尾插入右括号,也就是对于SR=(()(() 只允许在 (A()B(C()D ABCD四个位置插入右括号。

如此一来,只要在不同位置插入了不同数量的右括号,就一定得到不同的最终字符串。具体证明留给大家思考。

确定了插入的位置,我们还需要确定能插入右括号的数量。经过分析可以发现,对于每个位置,在该位置和之前允许插入的右括号数量是有上限的。

例如对于A和B(及之前),都是最多插入1个右括号,不然就会右括号过多造成不匹配。同理,C和D(及之前)最多插入2个右括号。

综上所述,对于SR,我们可以确定有若干个位置可以插入右括号,不妨设为M。同时每个位置能插入的右括号数量有上限,不妨设为limit[i]。limit[i]同样也可以用上述加1减1的方法求得。我们想知道在满足上述约束的情况下,总共插入CR个右括号有多少种方法。(还记得吗?每种方法都对应一种不同的最终字符串)

于是我们可以令f[i][j]表示在前i个位置一共插入了j个右括号有多少中方法。如果j > limit[i]则f[i][j] = 0;

否则 f[i][j] = f[i-1][0] + f[i-1][1] + ... f[i-1][limit[i-1]]。

以上是一个O(N^3)的DP,不过可以看出f[i][j]等于f[i-1]的一个前缀和,所以可以优化到O(N^2)。

  • 很巧妙的思路啊,学习了。 最后那个应该是 f[i][j] = f[i-1][0] + f[i-1][1] + ... f[i-1][min(j, limit[i-1])] 吧?

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享