问题描述
Description
We give the following inductive definition of a “regular brackets” sequence:
- the empty sequence is a regular brackets sequence,
- if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
- if a andb are regular brackets sequences, thenab is a regular brackets sequence.
- no other sequence is a regular brackets sequence
描述
给你一个字符串，里面只包含"(",")","[","]"四种符号，
如果：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的
For instance,all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()]
while thefollowing character sequences are not:
(, ], )(, ([)], ([(]
Given a brackets sequence of characters a1a2 … an,your goal is to find the length of the longest regular brackets sequence that is a subsequence ofs. That is, you wish to find the largestmsuch that for indicesi1,i2, …,imwhere 1 ≤i1 <i2 < … <im≤n,ai1ai2 …aim is a regular bracketssequence.
Given the initial sequence ([([]])], the longest regularbrackets subsequence is[([])].
Input
The input test file will contain multiple test cases. Each input test case consists of asingle line containing only the characters(,),[, and]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.
Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
Sample Input
((()))
()()()
([]])
)[)(
([][][)
end
Sample Output
6
6
4
0
6
步骤分析
见代码实现步骤
代码实现
public class Brackets {
private static String str = "([][][)" ;
public static void main(String[] args) {
//1、计算数据长度
int slen = str.length();
//2、生成动态规划数组dp
int[][] dp = new int[slen][slen];
//3、初始化dp
/* dp[i][j]：s[i]到s[j]之间包含的正确括号数
* i >= j => dp[i][j] = 0;
* 因为数组初始化为0，这道题不用再初始化
*/
//4、动态规划dp
/* 先算长度短的，再算长度长的
* s[i]匹配s[j]则 dp[i][j] = dp[i+1][j-1] + 2;
* 否则dp[i][j] = dp[i+1][j-1]
* 考虑到 ([])[] 这种情况，dp{[])[} = 2; dp{([])[]} 不等于 4而是等于dp{([])}+dp{[]}
* 所以需要再 dp[i][len]内部进行依次内更新k=i:j-1 dp[i][j] = max{dp[i][k]+dp[k+1][j]};
*/
for (int len = 2; len <= slen; len++)
for (int i = 0; i + len - 1 < slen; i++) {
int j = i + len - 1;
if(match(str.charAt(i),str.charAt(j)))
dp[i][j] = dp[i+1][j-1] + 2;
for (int k = i; k < j; k++)
if(dp[i][j] < dp[i][k]+dp[k+1][j])
dp[i][j] = dp[i][k]+dp[k+1][j];
}
System.out.println(dp[0][slen-1]);
// //3、初始化dp (以下的思路是有错误的)
// /* dp[i][j]：s[i]到s[j]之间包含的正确括号数
// * i >= j => dp[i][j] = 0;
// * 因为数组初始化为0，这道题不用再初始化
// */
// System.out.println();
// //4、动态规划dp
// /*
// * s[i]匹配s[j]则 dp[i][j] = dp[i+1][j-1] + 2;
// * 否则 dp[i][j] = dp[i+1][j-1]
// * 考虑到 ([])[] 这种情况，dp{[])[} = 2; dp{([])[]} 不等于 4而是等于dp{([])}+dp{[]}
// * 所以需要再 dp[i][j]内部进行依次内更新 k=j:-1:i+1 dp[i][j] = max{dp[i][k]+dp[k+1][j]};
// */
// for (int i = 0; i < len; i++)
// for (int j = i+1; j < len; j++) {
// //dp更新
// if(match(str.charAt(i),str.charAt(j)))
// dp[i][j] = dp[i+1][j-1] + 2;
// //dp[i][j]内更新
// for (int k = i+1; k < j; k++)
// if(dp[i][j] < dp[i][k]+dp[k+1][j])
// dp[i][j] = dp[i][k]+dp[k+1][j];
// }
//
//
// System.out.println(dp[0][len-1]);
}
private static boolean match(char l, char r) {
return l=='(' && r==')' || l=='[' && r==']'; //|| l=='{' && r=='}';
}
}
P.S.
需要至少添加多少个括号才能使这些括号匹配起来。
括号总数-最大匹配括号数。