nyoj 15 括号匹配（二）动态规划

当时看到（二）就把（一）做了，

一很容易，这道题纠结了好几天，直到今晚才看懂别人的代码谢，勉强才写出来。。。。。。。。。。。。。。。。。。。。

不愧是难度6的题。

#include <stdio.h>
#include <string.h>
#define N 101
#define MAX 0x7fffffff

int d[N][N];
char ch[N];

int main()
{
int n,i,j,k,len,m,tmp;
    scanf("%d",&n);

do
    {
        scanf("%s",ch);        
        len = strlen(ch);       

for(i = 0 ; i <= len ; ++i)
        {
            d[i][i] = 1;
for(j = 0; j < i ; ++j)
                d[i][j] = 0;
        }

for(k = 1 ; k < len ; ++k)
for(i = 0 ; i < len-k ; ++i)
            {
                j = i + k;
                d[i][j] = MAX;
if(( ch[i]== '[' && ch[j]==']') || ( ch[i]=='(' && ch[j] == ')'))
                    d[i][j] = d[i][j] < d[i+1][j-1] ?  d[i][j] : d[i+1][j-1];

for(m = i ; m < j ; ++m)
                {
                    tmp = d[i][m] + d[m+1][j];
if(tmp < d[i][j])
                        d[i][j] = tmp; 
                }

            }

            printf("%d\n",d[0][len-1]);
/*    for(i=0;i<=len;i++)
            {
                for(j=0;j<=len;j++)
                    printf("%d ",d[i][j]);
                printf("\n");
            }
*/

    }while(--n);  

return 0;
}