删括号 动态规划

   简单说下题意，给定两个有若干的括号的序列s和t，问可否在s中删除若干括号对后(或者不删除)，使得s序列成为t序列。

   看了好多题解，思想就是动态规划，我们需要定义dp[i][j][k],dp是bool类型即可，表示序列s在前i个并且删除掉k个左括号 ‘(’ 的情况下，可以与序列t的前j个匹配，如果删除了一个括号对，那么k就要相应的减一，所以最终判断的条件就是dp[len1][len2][0]是否为0，就是表示在恰好删除若干括号对的情况下相匹配。

   所以说在状态dp[i][j][k]=true的情况下，对于两个串的下一个字符，只有以下四种情况：

   对于第一种情况，可以推出dp[i+1][j+1][k]=true或dp[i+1][j][k+1]=true；对于第二种情况可以推出dp[i+1][j][k+1]=true；对于第三种情况可以推出dp[i+1][j+1][k]=true或dp[i+1][j][k-1]=true；对于第四种情况可以推出dp[i+1][j][k-1]=true；综合一下就是如果后一个字符相等且k=0，那么dp[i+1][j+1][0]=true，然后如果s的后一个字符是左括号，那么dp[i+1][j][k+1]=true，如果都不满足，并且k！=0，那么dp[i+1][j][k-1]=true.

   下面看一下代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    int len1=s.length();
    int len2=t.length();
    bool dp[105][105][55];
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=true;
    for(int q=0;q<len1;q++){
        for(int w=0;w<len2;w++){
            for(int e=0;e<len1/2;e++){
                if(dp[q][w][e]){
                    if(e==0&&s[q+1]==t[w+1]) dp[q+1][w+1][0]=true;
                    if(s[q+1]=='(') dp[q+1][w][e+1]=true;
                    else if(e) dp[q+1][w][e-1]=true;
                }
            }
        }
    }
    if(dp[len1][len2][0]) cout<<"Possible"<<endl;
    else    cout<<"Impossible"<<endl;
    return 0;
}

   自己最初犯了一个很纯的错误，把对dp[0][0][0]的赋值放到了memset前边。。。。