区间dp 括号匹配问题

这道题目能用区间dp来解决，是因为一个大区间的括号匹配数是可以由小区间最优化选取得到（也就是满足最优子结构）

然后构造dp

既然是区间类型的dp 一般用二维我们定义dp[i][j] 表示i~j这个区间需要添加括号的数量

那么状态怎么转移呢？

第一种情况：对于i指向的括号如果i+1 ~ j里面不存在与之匹配的括号那么dp[i][j] =dp[i+1][j]+1;

第二种情况：对于i指向的括号如果i+1~ j 里面存在与之匹配的括号下标我们记作k 那么在i+1 ~ j 中我们枚举所有的k

dp[i][j]=min(dp[i+1][k-1]+dp[k+1][j],dp[i][j]);

定义好状态转移方程以后后续的就是合理的对数据填充了应为dp[i]要用到dp[i+1]的结果所以我们这里自底向上的遍历

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstring>

using namespace std;

char s[101];

bool check(int i,int j)

{

    if(s[i]=='('&&s[j]==')' || s[i]=='['&&s[j]==']') return true;

    return false;

}

int main()

{

    int n;

    cin>>n;

    while(n--)

    {

        int dp[101][101];

        cin>>s;

        int len=strlen(s);

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

        for(int i=0;i<len;i++) dp[i][i]=1;

        for(int i=len-2; i>=0; i--)

        {

            for(int j=i; j<len; j++)

            {

                dp[i][j]=dp[i+1][j]+1;// 第一种情况我们先赋值，由于后续是最小值的比较 所以问题不大

                for(int k=i+1; k<=j; k++)

                {

                    if(check(i,k))// 如果匹配

                    {

                        dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j]);

                    }

                }

            }

        }

        cout<<dp[0][len-1]<<endl;//

    }

    return 0;

}

巴特西

区间dp 括号匹配问题

最新文章

热门文章