括号匹配（二）
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 6
- 描写叙述
- 给你一个字符串，里面仅仅包括"(",")","[","]"四种符号，请问你须要至少加入多少个括号才干使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的
- 输入
- 第一行输入一个正整数N，表示測试数据组数(N<=10) 每组測试数据都仅仅有一行，是一个字符串S，S中仅仅包括以上所说的四种字符，S的长度不超过100 输出
- 对于每组測试数据都输出一个正整数，表示最少须要加入的括号的数量。每组測试输出占一行 例子输入
-
4[]([])[]((]([)]
例子输出 -
0032
首先，这个问题详细是非常经典的区间动态规划问题，那么，我们能够使用一个二维数组dp[i][j] 表示字符串s的第i..j字符须要最少括号数，以下是详细的表示：
当i= j的时候，仅仅有一个字符，那么，仅仅要匹配一个字符即可了，所以，dp[i][i] = 1
如果，当i < j的时候，s[i] = s[j] 那么，dp[i][j] = min(dp[i][j],dp[i+1][j+1])，当中，如果i <= k < j 状态转移方程为 dp[i][j] = min(dp[i][j],d[i][k] + dp[k+1][j])
#include
#include #define min(x,y) (x < y ? x : y)#define MAX 101int dp[MAX][MAX];bool cmp(int n,int m){ if((n == '('&&m == ')')||(n == '['&&m == ']')) return 1; else return 0;}int main(void){ int n,m,i,j,k; char str[101]; scanf("%d",&n); while(n--) { scanf("%s",str); int length = strlen(str); memset(dp,0,sizeof(dp)); for(i = 0; i < length; i++) { dp[i][i] = 1; } for(m = 1; m < length; m++) { for(i = 0; i < length - m; i++) { j = i + m; dp[i][j] = MAX; if(cmp(str[i],str[j])) dp[i][j] = min(dp[i][j],dp[i+1][j-1]); for(k = i; k < j; k++) { dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]); } } } printf("%d\n",dp[0][length-1]); } return 0;}