Brackets：最长合法括号子序列
题意题目来源：POJ 2955 — Brackets。 给定一个只包含 (、)、[、] 的字符串，可以删除一些字符，但不能改变剩余字符的顺序。求能留下的最长合法括号序列的长度。输入包含多组数据，遇到 end 结束；每组输出一个答案。 做法用区间 DP。设 dp[i][j] 表示从第 i 个字符到第 j 个字符中，最多能选出多少个字符组成合法括号序列。单个字符不能配对，所以长度为 1 的区间答案是 0。 计算一个区间时，考虑两种情况： 如果两端是匹配的 () 或 []，就把它们选上，得到 dp[i+1][j-1]+2。 也可以从中间某处把区间分成左右两段，分别求答案再相加。枚举所有分割位置，取最大值。 按区间长度从小到大计算，最后输出 dp[0][n-1]。时间复杂度为 O(n^3)，空间复杂度为 O(n^2)。 C++ 代码123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;int main(){ string s; ...
