南阳理工大学oj 题目15 括号匹配(二)

括号匹配(二)

时间限制:1000 ms  |  内存限制:65535 KB

难度:6

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

如:

[]是匹配的

([])[]是匹配的

((]是不匹配的

([)]是不匹配的

输入第一行输入一个正整数N,表示测试数据组数(N<=10)

每组测试数据都只有一行,是一个字符串S,S中只包含以上所说的四种字符,S的长度不超过100输出对于每组测试数据都输出一个正整数,表示最少需要添加的括号的数量。每组测试输出占一行样例输入

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

样例输出

0
0
3
2

动态规划:区间DP

好久没写题目了,第一次写,有点生疏。还好是一遍过。要不然丢人了。

区间DP经典题:

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;

char a[105];
int dp[105][105];
int n;
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",a);
        
        for(int i=0;i<105;i++)
        {
            for(int j=0;j<105;j++)
            {
                dp[i][j]=100000;
                if(i==j)
                    dp[i][j]=1;
            }
        }
        int len=strlen(a);
        for(int j=1;j<len;j++)
        {
            for(int i=0;i<len&&i+j<len;i++)
            {
                int l = i;
                int r = i+j;
                if((a[l]=='['&&a[r]==']')||(a[l]=='('&&a[r]==')'))
                {
                    if(l==r-1)
                        dp[l][r]=0;
                    else
                        dp[l][r]=min(dp[l][r],dp[l+1][r-1]);
                }
                for(int k=l;k<r;k++)
                {
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
                }
            }
        }
        printf("%d\n",dp[0][len-1]);
        
    }
    
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java 泛型一览笔录

泛型(Generics )是把类型参数化,运用于类、接口、方法中,可以通过执行泛型类型调用 分配一个类型,将用分配的具体类型替换泛型类型。然后,所分配的类型将用...

941
来自专栏java一日一条

Java字符串之性能优化

在程序中你可能时常会需要将别的类型转化成String,有时候可能是一些基础类型的值。在拼接字符串的时候,如果你有两个或者多个基础类型的值需要放到前面,你需要显式...

802
来自专栏有趣的django

python面试题(持续更新)

第1~10题 1、一行代码实现1--100之和 >>> sum(range(1,101)) 5050 >>> 2、如何在一个函数内部修改全局变量 a= 3 ...

41911
来自专栏java一日一条

基础类型转化成String

在程序中你可能时常会需要将别的类型转化成String,有时候可能是一些基础类型的值。在拼接字符串的时候,如果你有两个或者多个基础类型的值需要放到前面,你需要显式...

792
来自专栏DT乱“码”

Java中实现多线程有两种途径

Java中实现多线程有两种途径:继承Thread类或者实现Runnable接口. Runnable接口非常简单,就定义了一个方法run(),继承Runnable...

2015
来自专栏java一日一条

Java字符串之性能优化

在程序中你可能时常会需要将别的类型转化成String,有时候可能是一些基础类型的值。在拼接字符串的时候,如果你有两个或者多个基础类型的值需要放到前面,你需要显式...

802
来自专栏HTML5学堂

2016.01.06 HTML5真题练习

HTML5学堂:每天一道题,强壮程序员!今日主要涉及01.05日,关于数组转换成字符串操作题目的解答,以及一道涉及数组操作的题目。 HTML5真题【2016.0...

2915
来自专栏数据结构与算法

3187 队列练习 3

3187 队列练习 3 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...

2665
来自专栏有趣的django

1.numpy的用法

782
来自专栏kalifaの日々

美团北京视频面试题目

1.用过makefile吗 2.python的多线程是真正的多线程吗? 3.写一个冒牌排序,再写一个递归的冒泡排序 4.写一个单链表反转,十几行代码以内 ...

832

扫码关注云+社区