最小添加括号数 dp记忆化

题目：

输入括号

输入：(注意有空行，用getline()或者gets()输入)

([(]

([(((])))

[]]]]]

 

)))(((

要求输出最小要加入的括号数目

分析：

   经典dp题，如果用dp自底向上的递推做的话，比较麻烦，其实用记忆化做很简单，

   每次递归前加上判断是否已经计算过即可减少计算量，相当于dfs里的剪枝，代码如下

 

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

#define X 205

#define INF 1000

int dp[X][X];

string s;

int f(int i,int j) //记忆化

{

   if(dp[i][j]!=-1)            //当计算过时

      return dp[i][j];

   if(i>j)                     //当前面的指针大于后面的指针时，已经结束这次递归

      return 0;

   if(i==j)                 //恰巧相等时，加一

      return 1;

   int ans = INF;

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

      ans = min(ans,f(i+1,j-1));  //当两者恰好能组成一对括号时

   else if(s[i]=='('||s[i]=='[')

      ans = min(ans,f(i+1,j)+1);  //当只有左边的一半时

   else if(s[j]==')'||s[j]==']')

      ans = min(ans,f(i,j-1)+1);  //当之有右边的一半时

   for(int k=i;k<j;k++)        //相当于最短路时的松弛操作

      ans = min(ans,f(i,k)+f(k+1,j));

   dp[i][j] = ans;             //用辅助数组储存状态，思想为用空间换取时间

   return ans;

}

int main()

{

   freopen("sum.in","r",stdin);

   freopen("sum.out","w",stdout);

   while(getline(cin,s))

   {

      memset(dp,-1,sizeof(dp));

      if(s.size())    //注意到有空行

         cout<<f(0,s.size()-1)<<endl;

      else

         cout<<endl;

   }

   return 0;

}