POJ 2995 Brackets 区间DP
题意
大意：给你一个字符串，询问这个字符串满足要求的有多少，()和[]都是一个匹配。需要注意的是这里的匹配规则。
解题思路
区间DP，开始自己没想到是区间DP，以为就是用栈进行模拟呢，可是发现就是不大对，后来想到是不是使用DP，但是开始的时候自己没有推出递推关系，后来实在想不出来看的题解，才知道是区间DP，仔细一想确实是啊。
下面就是状态转移方程：
[egin{cases}dp[i][j] &=& dp[i+1][j-1]+if(str[i]和str[j]匹配) \dp[i][j] &=& dp[i][k]+dp[k+1][j] & k=i+1,i+2,………j-1end{cases}
]
当初知道了转移方程，就自己写代码，可是就是不对，下面有两个代码，一个是错误的，一个是正确的，两个对比看一看原因。
代码实现
//这个是正确的
#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
", 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
", dp[0][len-1]);
}
return 0;
}