POJ 2955 Brackets --最大括号匹配,区间DP经典题
2024-10-16 14:38:22
题意:给一段左右小、中括号串,求出这一串中最多有多少匹配的括号。
解法:此问题具有最优子结构,dp[i][j]表示i~j中最多匹配的括号,显然如果i,j是匹配的,那么dp[i][j] = dp[i+1][j-1]+2;
否则我们可以分区间取最值。dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]); k在i,j之间。
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std; class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
vector<vector<int> > dp(n+);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
dp[i].push_back();
for(int len=;len<=n;len++) {
for(int i=,j;i<=n-len;i++) {
j=i+len-;
if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))
dp[i][j] = max(dp[i][j],dp[i+][j-]+);
for(int k=i;k<j;k++)
dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+][j]);
}
}
return dp[][n-];
}
}; int main()
{
Solution a;
string s;
while(cin>>s) {
if(s == "end") break;
cout<<a.longestValidParentheses(s)<<endl;
}
return ;
}
最新文章
- Python导出Excel为Lua/Json/Xml实例教程(二):xlrd初体验
- .Net 中的反射(动态创建类型实例) - Part.4
- 3098: Hash Killer II
- nmap端口状态解析
- Objective-C中NSValue的使用
- hdu 1532 Dinic模板(小白书)
- JAVA MemCache 史无前例的详细讲解【转】
- Java Apcahe的HTTPClient工具Http请求当请求超时重发
- GroupLayout 布局
- More lumber is required
- mysql的perror
- ubuntu 引导删除
- 关于echarts使用的各种问题
- Hibernate学习笔记二
- PEM routines:PEM_read_bio:no start line
- WebApp开发技术搭配
- 基本入门ISD9160开发指南
- read progress
- php 获取图片base64编码格式数据
- 我读《从Paxos到zookeeper分布式一致性原理与实践》
热门文章
- [WCF编程]12.事务:服务事务编程(下)
- [连载]《C#通讯(串口和网络)框架的设计与实现》- 5.串口和网络统一IO设计
- [C/C++] DebugBreak
- 1-7 basket.js localstorage.js缓存css、js
- [Android]Google 开源的 Android 排版库:FlexboxLayout
- iOS MJRefresh设置MJRefreshStateNoMoreData状态图片
- 来自沪江、滴滴、蘑菇街架构师的 Docker 实践分享
- 又一个高性能轻量级的iOS模型框架YYModel
- 记录一次Quartz2D学习(一)
- Android 高级面试题及答案