(区间dp 或 记忆化搜素 )Brackets -- POJ -- 2955

http://poj.org/problem?id=2955

 

 

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 and b are regular brackets sequences, then ab 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 the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a₁a₂ … a_n, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i₁, i₂, …, i_m where 1 ≤ i₁ < i₂ < … < i_m ≤ n, a_i1a_i2 … a_im is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single 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

 

 p[i][j]表示从i到j个可以组成的括号最大值，则若dp[i+1][j]已取到最大值，则dp[i][j] 的取值为 dp[i+1][j] ， 或若 s[i] 与 第i+1个到第j个中某个括号匹配（假定为第k个），则有dp[i][j] = max(dp[i+1][j], dp[i+1][k-1] + 2 + dp[k+1][j]) （注：要考虑k == i+1的情况要分开讨论)

 

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;const int INF = 0x3f3f3f3f;
#define N 105char s[N];
int  dp[N][N];int main()
{while(scanf("%s", s), strcmp(s, "end")){int i, j, k, len=strlen(s)-1;memset(dp, 0, sizeof(dp));for(i=len-1; i>=0; i--){for(j=i+1; j<=len; j++){dp[i][j] = dp[i+1][j];for(k=i+1; k<=j; k++){if((s[i]=='(' && s[k]==')') || (s[i]=='[' && s[k]==']')){if(k==i+1) dp[i][j] = max(dp[i][j], dp[k+1][j]+2);else       dp[i][j] = max(dp[i][j], dp[i+1][k-1]+dp[k+1][j]+2);}}}}printf("%d\n", dp[0][len]);}return 0;
}

 

记忆化索搜：

（感觉记忆化搜索只是把在递归中已经计算过的值给记录下来， 不知道是否理解有悟，慢慢用吧！！！）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>#define N 105
#define max(a,b) (a>b?a:b)char s[N];
int  dp[N][N];int OK(int L, int R)
{if((s[L]=='[' && s[R]==']') || (s[L]=='(' && s[R]==')'))return 2;return 0;
}int DFS(int L, int R)
{int i;if(dp[L][R]!=-1)return dp[L][R];if(L+1==R)return OK(L,R);if(L>=R)return 0;dp[L][R] = DFS(L+1, R);for(i=L+1; i<=R; i++){if(OK(L,i))dp[L][R] = max(dp[L][R], DFS(L+1, i-1)+DFS(i+1, R)+2);}return dp[L][R];
}int main()
{while(scanf("%s", s), strcmp(s, "end")){memset(dp, -1, sizeof(dp));printf("%d\n", DFS(0, strlen(s)-1));}return 0;
}