nyoj-括号匹配（二）---动态规划
生活随笔
收集整理的這篇文章主要介紹了
nyoj-括号匹配（二）---动态规划
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
括號(hào)匹配（二）
時(shí)間限制：1000?ms ?|? 內(nèi)存限制：65535?KB 難度：6 描述如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的 輸入
每組測(cè)試數(shù)據(jù)都只有一行，是一個(gè)字符串S，S中只包含以上所說(shuō)的四種字符，S的長(zhǎng)度不超過(guò)100
樣例輸出
0
0
3
2
求解分析：
以dp[i][j]表示從第i個(gè)字符到第j個(gè)字符需要添加的括號(hào)數(shù)量，則dp[i][i] = 1
有以下幾種狀態(tài)
1、若str[i] ==’(‘ && str[j] == ‘)’ || str[i] == ‘[' && str[j] == ‘]’,則dp[i][j] = min(dp[i][j],dp[i+1][j+1])
2、if(str[i] == ‘(‘ || str[i] == ‘[') ?ans[i][j] = min(ans[i][j],ans[i+1][j])+1;
3、if(str[j] == ‘)’ || str[j] == ‘]’) ans[i][j] = min(ans[i][j],ans[i][j-1])+1;
4、i到j(luò)可分為i—k和k+1—-j兩部分，在分別求解
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define inf 9831892 int dp[105][105]; int main() {int n,i,j,k,p;char s[105];scanf("%d",&n);while(n--){getchar();scanf("%s",s);int l=strlen(s);memset(dp,0,sizeof(dp));for(i=0;i<l;i++) dp[i][i]=1;for(p=1;p<l;p++){for(i=0;i<l-p;i++){j=i+p;dp[i][j]=inf;if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))dp[i][j]=min(dp[i][j],dp[i+1][j-1]);//如果匹配，取中間需要的括號(hào)；else if(s[i]=='['||s[i]=='(')dp[i][j]=min(dp[i][j],dp[i+1][j])+1;//如果是左括號(hào)，取其i+1~j位置需要括號(hào)最少的個(gè)數(shù)；else if(s[i]==')'||s[i]==']')dp[i][j]=min(dp[i][j],dp[i][j-1])+1;//如果是右括號(hào)，取其i~j-1位置需要括號(hào)最少的個(gè)數(shù)；for(k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//分割求和比較最少需要括號(hào)的個(gè)數(shù)；}}printf("%d\n",dp[0][l-1]);} }總結(jié)
以上是生活随笔為你收集整理的nyoj-括号匹配（二）---动态规划的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 中台是个筐，啥都往里装？
- 下一篇： nyoj-Human Gene Func