POJ2955 Brackets 动态规划 - c++编程基础

区间DP，给你一个字符串，请输出最大匹配数*2，其中()匹配，[]匹配，

本来的想法是分开写，不过是要正着找，一个是区间[i,j]若 s[i] == s[j]的时候，方程是dp[i][j] = max(dp[i+1][j-1] + 1,dp[i][k]+dp[k+1][j])，若不相等那就更好办了dp[i][j] = max(dp[i][j],dp[i][k] + dp[k+1][j]);这样是可以的

后来想想其实还有更简洁的,倒着找，先假设不匹配那么 dp[i][j] = dp[i+1][j]，接下来去寻找[i+1,j]内有没有相同的，就像Light OJ1422一样，有的话那么dp[i][j] = max(dp[i][j],dp[i][k-1]+dp[k][j] + 1);

以前做过一道类似的用的是第一种，今天做过LightOJ1422以后就想到了第二种

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) string s; int dp[1000 + 5][1000 + 5]; void clear() { memset(dp,0,sizeof(dp)); } int main() { while(cin>>s) { if(s == "end")break; clear(); for(int i=s.length()-1;i>=0;i--) { for(int j=i+1;j