Week12 作业 D

题目描述：

一串包括( 、) 、[ 、]的括号序列，找出一个最长的子序列，使这个子序列是一个合法的括号序列，输出最长的子序列的长度

思路：

定义状态：F[i][j]表示子串s[i...j]能得到的最长序列

状态转移：F[i][j]=max{ F[i][k]+F[k+1][j] , i<=k<j } ，如果s[i]和s[j]匹配，则还应有F[i][j]=max{ f[i][j] , f[i+1][j-1]+2 }

边界条件：F[i][i]=0

答案：F[0][N-1]（字符串从0开始编号）

代码：

记忆化搜索

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <string>
 6 using namespace std;
 7 const int MAXN = 105;
 8 int f[MAXN][MAXN];
 9 bool vis[MAXN][MAXN];
10 string s;
11 int dp(int i, int j)
12 {
13     if (i == j) return f[i][j] = 0;
14     if (vis[i][j]) return f[i][j];
15     vis[i][j] = 1;
16     if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))
17         f[i][j] = dp(i + 1, j - 1) + 2;
18     for (int k = i; k <= j - 1; k++)
19         f[i][j] = max(f[i][j], dp(i, k) + dp(k + 1, j));
20     return f[i][j];
21 }
22 int main()
23 {
24     while (cin >> s)
25     {
26         if (s[0] == 'e') break;
27         memset(f, 0, sizeof(f));
28         memset(vis, 0, sizeof(vis));
29         int N = s.size();
30         cout << dp(0, N-1) << endl;
31     }
32     return 0;
33 }

View Code

考虑编写递推的实现形式：发现记忆化搜索的过程中，子问题的区间长度，是比当前问题要小的，所以我们可以枚举区间长度，来顺序递推

确定了计算顺序，就能保证子问题一定先被求解完，就可以安心递推了

递推（确实比记忆化快）

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int MAXN = 105;
int f[MAXN][MAXN];
string s;
int main()
{
	while (cin >> s)
	{
		if (s[0] == 'e') break;
		memset(f, 0, sizeof(f));
		
		int N = s.size();
		for (int len = 2; len <= N; len++)
		{
			for (int i = 0; i <= N - len; i++)	//枚举[0,1],[1,2]....[0,2],[1,3]....[0,3][1,4]....
			{
				int j = i + len - 1;
				if ((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))
					f[i][j] =f[i+1][j-1]+ 2;
				for (int k = i; k <= j - 1; k++)
					f[i][j] = max(f[i][j], f[i][k] + f[k+1][j]);
			}
		}
		cout << f[0][N - 1] << endl;
	}
	return 0;
}