一道面试题及其扩展，求好解法

1、原始题目

看到一道大家讨论的比较老的算法面试题，说是字符串pStr，其中包含有大括号“{""}"中括号"[""]"小括号"("")"试编写一个递归函数，判断表达式中的括号是否匹配，返回true或者false。这道题之前自己准备面试的时候也做到过，好像是Catalan数的一个应用，用一个栈还是能很好地实现的，博主的代码如下。

#include <vector>
using namespace std;


bool isMatch(const char* pStr)
{
    const char* p = NULL;
    p = pStr;

    vector<char> Stack;

    while(*p)
    {
        if (   (*p != '{') && (*p != '}') 
            && (*p != '[') && (*p == ']') 
            && (*p != '(') && (*p != ')')
           )
        {
            if (Stack.empty())
            {
                return (false);
            }
            p++;
        }
        else if ((*p == '{') && (*p != '[') && (*p != '('))
        {
            Stack.push_back(*p);
            p++;
        }
        else if ((*p == '}') && (*p != ']') && (*p != ')'))
        {
            char c = '\0';
            if (Stack.empty())
            {
                return (false);
            }
            
            c = Stack[Stack.size() - 1];        
            if (   ('{' == c) && (*p == '}') 
                || ('[' == c) && (*p == ']') 
                || ('(' == c) && (*p == ')') 
               )
            {
                Stack.pop_back();
                p++;
                continue;
            }

            return (false);
        }
    }

    return (Stack.empty());
}


int main()
{
    const char *p = "{}";
    
    printf("%s\n", isMatch(p)? "True": "False");

    getchar();
}

2、附加要求

但是最近看到的要求是用递归写，整个实现不可以出现一个循环语句，大家有什么好的想法吗，我看了一部分童鞋的讨论，也粘贴在下面了。

@Eul_82：这个问题用到一个性质:左数第一个右括号的左邻括号，正是右括号的匹配括号。因此递归函数可以有两个参数:左括号栈，余下数组。每次递归取余下数组的首项，如果是左括号则进左括号栈;如果是右括号则左括号栈顶出栈;继续递归直到两个参数都空为止，此时输出yes，否则输出no n的复杂度上限。

@这名字也被起了：尾递归+stack，O(n)

@岩少想做猎命师：感觉像是Catalan数的应用，任何一个时刻左括号的数目不应该小于右括号的数目，那维护一个变量，初始为0，判断当前字符，为左括号则变量+1，否则-1，变量减小到负数则直接退出，否则下标加一，传参递归。

3、题目扩展

给你一个字符串，里面只包含"(",")","[","]","{","}"几种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
例如：
[]是匹配的，所需括号个数为 0；([])[]是匹配的，所需括号个数为 0；((]是不匹配的，所需最少括号个数为 3；([)]是不匹配的，所需最少括号个数为 2.

这道变种题大多数人的解题思路都是动态规划，思路如下。不知道大家有没有好的别的方法，求教。

1）用 dp[i][j] 表示从位置 i 到字符位置 j 所需的最少括号数。假定字符串是 “[ ( )”, 那么 dp[0][0] = dp[1][1] = dp[2][2] = 1。

2）如果我们要算dp[i][j+1], 那么，最坏的情况是使得没有被匹配的括号数增加了，即 dp[i][j+1] 最多为 min( dp[i][j] + 1, dp[i+1][j+1] + 1). 但是，这可能不是我们想要的答案，因为在刚才的例子里，即：假定字符串是 “[ ( )”, 那么 dp[0][1] =dp[0][0] + 1= 2， 但是dp[1][2] 却不等于dp[1][1] + 1.

3）那么，什么情况下dp[i][j+1] =dp[i][j] + 1？只有当 字符串里从i 到 j 没有任何字符与第 j + 1 个字符匹配的时候。但是，如果存在和第 j + 1 个字符匹配的情况，问题就不一样了。

4）假设在i 到 j 之间存在一个字符（比如在位置 k）与第 j + 1 个字符匹配，那么我们相当于把原来的字符串分成了两个部分dp[i][k-1] 和 dp[k+1][j], 因为第k 个 和 j + 1 个字符已经匹配掉了。而且，我们不会再考虑 i 到 k - 1 的字符会和 k + 1 到 j 之间的字符匹配的情况，因为我们已经把这两个部分完全分开了。话句话说 dp[i][j+1] = min(min(dp[i][j] + 1, dp[i+1][j+1] + 1), dp[i][k-1] + dp[k+1][j]).

#include<iostream>
#include<string>
#include<memory.h>
using namespace std;
bool is(char a, char b){
	if(a == '(' && b == ')')
		return 1;
	if(a == '[' && b == ']')
		return 1;
	if(a == '{' && b == '}')
		return 1;
	return 0;
}
int main(){
	//dp[i][j] 表示从第i位至第j位的最小匹配长度
	int t, i, j, k, dp[105][105];
	cin >> t;
	while(t--){
		string s;
		cin >> s;
		memset(dp, 0, sizeof(dp));
		for(i = 0; i <= s.length(); ++i){
			dp[i][i] = 1;
		}
		for(i = 2; i <= s.length(); ++i){
			for(j = i - 1; j >= 1; --j){
				dp[j][i] = dp[j][i - 1] + 1;
				for(k = j; k < i; ++k){
					if(is(s[k - 1], s[i - 1])){
						dp[j][i] = min(dp[j][i], dp[j][k - 1] + dp[k + 1][i - 1]);
					}
				}
			}
		}
		cout << dp[1][s.length()] << endl;
	}
	return 0;
}