NYOJ 题目15 括号匹配(二)(区间DP)

点我看题目

题意 : 中文题不详述。

思路 : 本来以为只是个小模拟,没想到是个区间DP,还是对DP不了解。

DP[i][j]代表着从字符串 i 位置到 j 位置需要的最小括号匹配。

所以初始化的DP[i][i] = 1 ;第i个位置的话需要匹配的最小括号数是1。

状态转移方程 :如果第i个位置和第j个位置的两个括号是匹配的,那么DP[i][j] = DP[i+1][j-1],相当于两边分别往里缩了一个;当i < j 时,DP[i][j] = DP[i][k]+DP[k+1][j] ;

黑书上对于这个问题有详细的解释。我用的就是黑书上的方法二,不过方法二有点赘余,就是我代码中注释的部分,加上也对,不加也可。

 #include <stdio.h>
#include <string.h>
#include <iostream> using namespace std ; int dp[][] ;
char ch[] ; int main()
{
int n ;
scanf("%d",&n) ;
getchar() ;
while(n--)
{
scanf("%s",ch);
memset(dp,,sizeof(dp)) ;
int len = strlen(ch) ;
for(int i = ; i < len ; i++)
dp[i][i] = ;
for(int h = ; h < len ; h++)
{
for(int i = ; i < len-h ; i++)
{
int j = h+i ;
dp[i][j] = ;
if((ch[i] == '('&&ch[j] == ')') || (ch[i] == '[' && ch[j] == ']'))
dp[i][j] = min(dp[i][j],dp[i+][j-]) ;
// else if(ch[i] == '(' || ch[i] == '[')
// dp[i][j] = min(dp[i][j],dp[i+1][j])+1 ;
// else if(ch[j] == ')' || ch[j] == ']')
// dp[i][j] = min(dp[i][j],dp[i][j-1])+1 ;
for(int k = i ; k <= j ; k++)
dp[i][j] = min(dp[i][j],dp[i][k-]+dp[k][j]) ;
}
}
printf("%d\n",dp[][len-] ) ;
}
return ;
}
上一篇:P1486 [NOI2004]郁闷的出纳员


下一篇:Java线程池的拒绝策略