非曰能，好学。欢迎大家一起交流学习

题目描述

链接：https://ac.nowcoder.com/acm/problem/21303

给你一个合法的括号序列s1，每次你可以删除一个"()"
你可以删除0个或者多个"()"
求能否删成另一个括号序列s2

问题分析

看答案，大家都用的动态规划，这里提供一个递归解法。
括号可以批成一组一组的，如下图所示，s1被分为两组，s2只包括一组。

怎么分组呢？对字符串中的左括号右括号计数，相等的时候，即为一组的结束位置。为了使得s1能0个或者多个"()"变成s2，需要s1中从前往后去pk s2中的组，若是能pk过，则去pk下一组，类似于判定一个字符串是否为另一个字符串的子序列

那怎么判断s1中的一组括号能pk过s2中一组括号呢？显然如上图所示s1的第一组是干不过s2中括号组，但是s1的第二组可以干过s2中括号组。总结规律可以得到：将预对比的两组括号，分别去掉开头和结尾，pk剩下的两括号字符串，而pk剩下的两括号字符串即原问题本身，从而完成递归。

代码实现

最后附上本人拙劣的代码，耗时6ms，内存消耗相比动态规划小很多

#include <bits/stdc++.h>
using namespace std;

class Solution 
{
    public:
        string s1;
        string s2;
        void read()
        {
            cin>>s1;
            cin>>s2;
        }

        int getNext(const string& S, int is)
        {
            int lcnt=0;
            int rcnt=0;
            while(is<S.size())
            {
                if(S[is]=='(')
                    lcnt++;
                else
                    rcnt++;
                if(rcnt==lcnt)
                    return is;
                is++;
            }
            return is;
        }

        // 多组原子对多组原子
        bool isMatch(int l1, int r1, int l2, int r2)
        {
            int i1,i2,j1,j2;
            j1=l1-1;
            i2=l2;
            j2=getNext(s2,i2);

            while(j2<=r2)
            {
                while(1)
                {
                    i1=j1+1;;
                    if(i1>r1)
                        return false;
                    j1=getNext(s1,i1);
                    if( isCover(i1,j1,i2,j2) )
                    {
                        i2=j2+1;
                        if(i2>r2)
                            return true;
                        j2=getNext(s2,i2);
                        break;
                    }
                }
            }
            return true;
        }

        //s1的从l1到r1,能cover住s2的l2到r2吗， l1-l1是个原子,即(xxx)
        bool isCover(int l1, int r1, int l2, int r2)
        {
            if(r1-l1<r2-l2)
                return false;
            if(l2+1==r2)
                return true;
            return isMatch(l1+1,r1-1, l2+1,r2-1);

        }
        void process()
        {
            read();
            if(isMatch(0,s1.size()-1, 0, s2.size()-1))
                cout<<"Possible"<<endl;
            else
                cout<<"Impossible"<<endl;
            return ;
        }
};

int main()
{
    Solution s;
    s.process();
    return 0;
}