nyoj 15括号比對 （動态規劃）

     NYOJ  15 括号比對

給你一個字元串，裡面隻包含"(",")","[","]"四種符号，請問你需要至少添加多少個括号才能使這些括号比對起來。

如：

[]是比對的

([])[]是比對的

((]是不比對的

([)]是不比對的

輸入

第一行輸入一個正整數N，表示測試資料組數(N<=10)

每組測試資料都隻有一行，是一個字元串S，S中隻包含以上所說的四種字元，S的長度不超過100

輸出

對于每組測試資料都輸出一個正整數，表示最少需要添加的括号的數量。每組測試輸出占一行

樣例輸入

4
[]
([])[]
((]
([)]      

樣例輸出

0
0
3
2      

去年暑假，就在思考這個問題，今天終于解決了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 102
#define INF 1e9
int result[N][N];//儲存從i 到 j所需要的最少括号數
char s[N];
int Min(int i,int j)
{
   if(result[i][j]!=INF)
      return result[i][j];
   else
   {
      for(int t=i;t<j;t++)
      {
         int tempa=Min(i,t);
         int tempb=Min(t+1,j);
         //如果第i 和 第j 比對的話，那麼result[i][j]=result[i+1][j-1]
         if(s[i-1]=='('&&s[j-1]==')'||(s[i-1]=='['&&s[j-1]==']'))
           result[i][j]=min(result[i][j],result[i+1][j-1]);
           
           result[i][j]=min(result[i][j],tempa+tempb);
      }
      return result[i][j];
   }
}
int main()
{
   int n,T,i,j;
   cin>>T;
   while(T--)
   {
      scanf("%s",s);
      n=strlen(s);
      for(i=1;i<=n;i++)
         for(j=i+1;j<=n;j++)
         {
           result[i][j]=INF;
         }
      result[n][n]=1;
      for(i=1;i<n;i++)
      {
         result[i][i]=1;
         result[i+1][i]=0;
      }
      cout<<Min(1,n)<<endl;
    /*  cout<<"************"<<endl;
      for(i=1;i<=n;i++)
       {

          for(j=1;j<=n;j++)
         {
           cout<<result[i][j]<<" ";
         }
         cout<<endl;
       }*/
   }
    return 0;
}