分组符号最大长度平衡子序列 [英] Grouping Symbols Maximum Length Balanced Subsequence

问题描述

考虑乙成为分组符号的序列（，），[，]，{和}。 B被称为一个平衡序列，如果它是一个长度为0的或B是下列形式之一：{X} Y或[X] Y或{X} Y，其中X和Y平衡自己。举例平衡：（） - {[]（）} [] - ...

Consider B to be a sequence of grouping symbols (, ), [, ], {, and }. B is called a Balanced sequence if it is of length 0 or B is of one of the following forms: { X } Y or [ X ] Y or { X } Y where X and Y are Balanced themselves. Example for Balanced : ( ) - { [ ] ( ) } [ ] - ...

现在的问题是找到一个有效的算法找出最大长度平衡子（不一定是连续的）给定的输入是这些分组符号的字符串。

Now the question is to find an efficient algorithm to find maximum length balanced subsequence (not necessarily contiguous) of a given input which is an string of these grouping symbols.

例如，如果输入的（）{（）{（]）}} [] ，最大长度子序列中的一个是（）{[] {（） }} []

For example if input is ( ) { ( [ ) ] { ( ] ) } } [ ] , one of the max-length subsequences is ( ) { [ ] { ( ) } } [ ]

我几乎可以肯定的解决方案是DP，但无论如何，我解决这个问题，我觉得例子，其中我的算法是行不通的。只有一个方法我可以肯定，这是DP和分而治之的组合。但它是没有效率，因为反正D＆放大器; C部分，会一遍又一遍，以解决一些重叠的问题。

I am almost sure the solution is DP but anyway I solve it I find examples in which my algorithm doesn't work. there is only one approach I am sure about, which is a combination of DP and Divide and Conquer. But it is not efficient because anyway D&C part is going to solve some overlapping problems over and over again.

推荐答案

让我们做一些简单的观察：

Let's make a couple of simple observation:

1. psented为

   任何平衡子可以重新$ P $ A1 X A2是，其中 A1 和 A2 的两个匹配的括号（（），[]或{}）， X 和是是平衡的子序列（也可以是空的）。这是事实，因为在任何平衡非空子序列最左边的支架，它必须匹配的东西。

1. Any balanced subsequence can be represented as A1 X A2 Y, where A1 and A2 are two matched brackets((), [] or {}), X and Y are balanced subsequences(they can be empty). It is true because there is a leftmost bracket in any balanced non-empty subsequence and it must be matched to something.

X 和是是独立的。如果不是的情况下，亚序列是不均衡的。

X and Y are independent. If it is not the case, the subsequence is not balanced.

这些观察结果给我们一个动态规划的解决方案：

These observations give us a dynamic programming solution:

假设 F（L，R）是最长的平衡子[L，R] 子阵。 碱是空的子阵列。过渡如下：

Let's assume f(L, R) is the longest balanced subsequence for [L, R] subarray. The base is an empty subarray. Transition are as follows:

f(L, R) = max(   
     f(L + 1, R) // ignore the first element    
     max(f(L + 1, K - 1) + 2 + f(K + 1, R)) for all K if brackets at positions L and K match
)

时间复杂度为 O（N ^ 3）因为有 O（N ^ 2）子阵列和有 O（N）转换为他们每个人。有可能使用标准答案重建技术重建最长序列本身。

The time complexity is O(N^3) because there are O(N^2) subarrays and there are O(N) transitions for each of them. It is possible to reconstruct the longest subsequence itself using standard answer reconstruction techniques.

这篇关于分组符号最大长度平衡子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！