学步园

经典DP题啊，看着黑书学的。

虽然它作为DP来讲，算是很水吧，不过说下我的理解吧。

枚举步长，相隔0个字符的两个字符，相隔1个的，相隔2个的。。等等。

假设在求相隔N个的字符时的两个字符的情况时，他俩中间的所有情况都已经考虑到了，所以只需要把他划分一下（划分成，(1,x )+ (x,N）然后用小区间去更新大区间，而这些小区间都是已经匹配了的。

明显突出了最优子结构以局部推整体。

很神奇~

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>

using namespace std;

const int MAX = 110;
char s[MAX];
int dp[MAX][MAX];
int main()
{
	int ncases;
	
	scanf("%d",&ncases);
	
	while( ncases-- )
	{
		scanf("%s",s);
		memset(dp,0,sizeof(dp));
		int n = strlen(s);
		for(int i=0; i<n; i++)
			dp[i][i] = 1;
			
		for(int i=1; i<n; i++)
			for(int k=0; k<n-i; k++)
			{
				int j = i+k;
				dp[k][j] = INT_MAX;
				if( s[k] == '(' && s[j] == ')' || s[k] == '[' && s[j] == ']' )
					dp[k][j] = min(dp[k][j],dp[k+1][j-1]);
				else
					if( s[k] == '(' || s[k] == '[' )
						dp[k][j] = min(dp[k][j],dp[k+1][j]+1);
					else
						dp[k][j] = min(dp[k][j],dp[k][j-1]+1);
				for(int p=k; p<j; p++)
					dp[k][j] = min(dp[k][j],dp[k][p]+dp[p+1][j]);
			}
		printf("%d\n",dp[0][n-1]);
	}

return 0;
}

刚看了nyist的标程，只需要一个判断就行了 T T 。。。也是。。。

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>

using namespace std;

const int MAX = 110;
char s[MAX];
int dp[MAX][MAX];
int main()
{
	int ncases;
	
	scanf("%d",&ncases);
	
	while( ncases-- )
	{
		scanf("%s",s);
		memset(dp,0,sizeof(dp));
		int n = strlen(s);
		for(int i=0; i<n; i++)
			dp[i][i] = 1;
			
		for(int i=1; i<n; i++)
			for(int k=0; k<n-i; k++)
			{
				int j = i+k;
				dp[k][j] = INT_MAX;
				if( s[k] == '(' && s[j] == ')' || s[k] == '[' && s[j] == ']' )
					dp[k][j] = min(dp[k][j],dp[k+1][j-1]);
					
				for(int p=k; p<j; p++)
					dp[k][j] = min(dp[k][j],dp[k][p]+dp[p+1][j]);
			}
		printf("%d\n",dp[0][n-1]);
	}

return 0;
}