NYoj 15 括号匹配（二）[动态规划.有点难]

本文主要是介绍NYoj 15 括号匹配（二）[动态规划.有点难]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*NYoj 15 括号匹配（二）动态规划.没有理解，以后的学习一定要弄懂.状态转移方程:dp[i][j]=min{dp[i+1][j-1](a[i]a[j]=='()'||a[i][j]=='[]')  dp[i][k]+dp[k+1][j](i<=k<j)}
*/
#include<iostream>
#include<cstring>
#include<stdio.h>
#define N 105
#define min(a,b) a>b?b:a
using namespace std;
int d[N][N];
char a[N];
int main()
{int T;cin>>T;while(T--){cin>>a+1;//a+1代表a字符串从下标开始.int n=strlen(a+1);for(int i=1;i<=n;i++) d[i][i-1]=0;for(int i=1;i<=n;i++) d[i][i]=1;for(int p=1;p<=n-1;p++){for(int i=1;i<=n-p;i++){int j=i+p;d[i][j]=1000;if((a[i]=='('&&a[j]==')')||(a[i]=='['&&a[j]==']'))d[i][j]=min(d[i][j],d[i+1][j-1]);for(int k=i;k<j;k++)//这里没有考虑[()]这种情况d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);}}printf("%d\n",d[1][n]);}return 0;
}

这篇关于NYoj 15 括号匹配（二）[动态规划.有点难]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---