POJ 2995 Brackets 区间DP

题意

大意：给你一个字符串，询问这个字符串满足要求的有多少，()和[]都是一个匹配。需要注意的是这里的匹配规则。

解题思路

区间DP，开始自己没想到是区间DP，以为就是用栈进行模拟呢，可是发现就是不大对，后来想到是不是使用DP，但是开始的时候自己没有推出递推关系，后来实在想不出来看的题解，才知道是区间DP，仔细一想确实是啊。

下面就是状态转移方程：

当初知道了转移方程，就自己写代码，可是就是不对，下面有两个代码，一个是错误的，一个是正确的，两个对比看一看原因。

代码实现

//这个是正确的

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e3+7;

char str[maxn];

int dp[maxn][maxn];

int main()

{

	while(scanf("%s", &str))

	{

		if(strcmp("end", str)==0)

			break;

		int n=strlen(str);

		memset(dp, 0, sizeof(dp));

        //下面书写的格式很重要，先算长度为1的区间，然后再算区间为2的区间，以此类推

		for(int len=1; len<=n; len++)

		{

			for(int L=0; L+len<n; L++)

			{

				int R=L+len;

				if((str[L]=='(' && str[R]==')') || (str[L]=='[' && str[R]==']'))

				{

					dp[L][R]=dp[L+1][R-1]+2;

				}

				for(int k=L; k<R; k++)

				{

					dp[L][R]=max(dp[L][R], dp[L][k]+dp[k+1][R]);

				}

			}

		}

		printf("%d\n", dp[0][n-1]);

	}

	return 0;

}

//这个是错误的代码，下面分析主要原因，连样例都过不了

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<stack>

using namespace std;

stack<char> st;

const int maxn=1e4+7;

char str[maxn];

int dp[maxn][maxn];

int main()

{

	while(scanf("%s", str))

	{

		if(strcmp("end", str)==0)

			break;

		int n=strlen(str);

		memset(dp, 0, sizeof(dp));

        //下面的代码其实是有点问题的，应该是先算长度全为1的区间段，然后再是长度为2的，以此类推

        //为什么要这这样呢，因为下面的max函数中第二项是一个重要的部分

		for(int L=0; L<len; L++)

		{

			for(int R=i+1; R<len; R++)

			{

				dp[L][R]=dp[L+1][R-1];

				if(str[L]=='(' && str[R]==')' || str[L]=='[' && str[R]==']')

				{

					dp[L][R]+=2;

				}

				for(int k=L; k<R; k++)

				{

                    //下面的后两项之和应该在计算dp[L][R]之前就应该计算了，但是这里可能没有。

                    //所以区间DP的书写格式还是有点套路的。

					dp[L][R]=max(dp[L][R], dp[L][k]+dp[k+1][R]);

				}

			}

		}

		printf("%d\n", dp[0][len-1]);

	}

	return 0;

}