括号匹配（二）

描述

给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

输入

第一行输入一个正整数N，表示测试数据组数(N<=10)
每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符，S的长度不超过100

输出

对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组测试输出占一行

样例输入

4
[]
([])[]
((]
([)]

样例输出

0
0
3
2

分析：dp[i][j]――从i到j需要添加的括号数，枚举i到j距离m( 1 ~ (len-1) ) 当s[i]和s[j]匹配时： dp[i][j]=min( dp[i][j] ,dp[i+1][j-1] ) , dp[i][j]=min( dp[i][j], dp[i][k]+dp[k+1][j] ) 代码：

#include 
      
       
#include 
       
         int min(int x, int y) { if (x > y) return y; return x; } int dp[150][150]; int main() { int n, m, i, j, k; char s[101]; scanf("%d", &n); while (n--) { scanf("%s", s); int len = strlen(s); memset(dp, 0, sizeof(dp)); for (i = 0; i < len; i++) dp[i][i] = 1; // 一个字符匹配数为1 for (m = 1; m < len; m++) { for (i = 0; i < len - m; i++) { j = i + m; dp[i][j] = 150; if ((s[i] == '('&&s[j] == ')') || (s[i] == '['&&s[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][len - 1]); } return 0; }
       
      

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??

上一篇： RMQ uva11235

下一篇： poj3190Stall Reservations(贪心+优先队列)

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");