O(1) 的小樂

DIV 2 1000

給定一個(gè)字符串([{}])()[]{} 這有這樣六種括號(hào)，求至少改變多少個(gè)括號(hào)可以使其變成規(guī)則匹配的？

一個(gè)經(jīng)典的DP，O(n^2)的狀態(tài)空間， 就是字串的數(shù)目，然后O(n)的轉(zhuǎn)移方程類似于矩陣乘法。轉(zhuǎn)移方程一定要想清楚

int dp[55][55];
int cost(char a, char b)
{
    if(a == '(' && b==')'|| a=='{' && b=='}'|| a=='[' && b==']') return 0;
    else if(a=='(' || a == '[' || a=='{' || b==')'|| b=='}'|| b==']') return 1;
    else return 2;
}
class CorrectingParenthesization
{
        public:
        int getMinErrors(string s)
        {
            memset(dp, 0 ,sizeof(dp));
            int M = s.size();
            for(int i=1; i<M; i++) // internal
            {
                if(i%2==0) continue;
                for(int j=0; j<M;j++)
                {
                    dp[j][j+i] = dp[j+1][j+i-1] + cost(s[j], s[j+i]);
                    for(int k=1; k<i; k++ )
                    {
                        if(k%2==0) continue;
                        dp[j][j+i] = min(dp[j][j+i], dp[j][j+k]+dp[j+k+1][i+j]);
                    }
                }
            }
            return dp[0][M-1];
        }
};