【C++动态规划】有效括号的嵌套深度

本文涉及知识点

C++动态规划

LeetCode1111. 有效括号的嵌套深度

有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示：

给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。
不相交：每个 seq[i] 只能分给 A 和 B 二者中的一个，不能既属于 A 也属于 B 。
A 或 B 中的元素在原字符串中可以不连续。
A.length + B.length = seq.length
深度最小：max(depth(A), depth(B)) 的可能取值最小。
划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
answer[i] = 0，seq[i] 分给 A 。
answer[i] = 1，seq[i] 分给 B 。
如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
示例 1：
输入：seq = “(()())”
输出：[0,1,1,1,1,0]
示例 2：
输入：seq = “()(())()”
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = “()()”, B = “()()”, max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = “()()()”, B = “()”, max(depth(A), depth(B)) = 1 。
提示：
1 < seq.size <= 10000

有效括号字符串：
仅由 “(” 和 “)” 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：

1. 空字符串

2. 连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串

3. 嵌套，可以记作 (A)，其中 A 是有效括号字符串
   嵌套深度：
   类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：

4. s 为空时，depth(“”) = 0

5. s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串

6. s 为嵌套情况，depth(“(” + A + “)”) = 1 + depth(A)，其中 A 是有效括号字符串
   例如：“”，“()()”，和 “()(()())” 都是有效括号字符串，嵌套深度分别为 0，1，2，而 “)(” 和 “(()” 都不是有效括号字符串。

简化后的问题：求最小max(a的深度,b的深度)

和本题没直接关系，类似而已。本方法可以求解，只是太麻烦。
如果s[i]为左括号，其权值为1；为右括号，其权值为-1。p[i]记录s[0…i]的权值和。
pa[i]记录s[0…i]中被a选中的权值和。pb[i]记录s[0…i]中被b选中的权值和。
根据括号的等效条件：
条件一， ∀ \forall ∀i,p[i]，pa[i],pb[i]都>=0。
条件二：p.back() pa.back() pb.back()都为0。
令f(left,right) 记录s[left…right]中被拆分A，B部分，的最大深度。
推论一：如p[i]等于0，则s[0…i]和s[i+1…n-1]都是合法括号。
推论二：如p[i]等于0，则pa[i]和pb[i]都等于0,即a,b都可以通过s[i]拆分。
推论三：如果s[i] ==0 ,则f(0,n-1) = max(f(0,i),f(i+1,n-1))。
令 11,i2 = g(left,right) 记录s[left…right]，i1是A的深度，i2是b的深度。确保max(i1,i2)最小。
推论四：除了p.back()外p[i]全大于0，则
i3,i4 = g(left+1,right-1) , i1 = min(i3,i4)+1 i2 = max(i3,i4)
如果left > right，则返回{0,0}
时间复杂度：O(nn) ∀ \forall ∀i，每层s[i]都只会处理一次。

代码

class Solution {
		public:
			int maxDepthAfterSplit(string seq){
				function<pair<int,int>(int,int)> Do = [&](int left, int right)-> pair<int, int> {
					if (left > right) { return  make_pair(0,0);  }
					int cur = 0;
					for (int i = left; i < right; i++) {
						cur += ('(' == seq[i]) ? 1 : -1;
						if (cur == 0) {							
							auto [i1, i2] = Do(left,i);
							auto [i3, i4] = Do(i+1, right);
							vector<int> is = { i1,i2,i3,i4 };
							sort(is.begin(), is.end());
							return { is[1] ,is.back() };
						}
					}
					auto [i1, i2] = Do(left+1,right-1);
					return { min(i1,i2) + 1,max(i1,i2) };
				};
				auto [i1, i2] = Do(0, seq.length() - 1);
				return max(i1, i2);
			}
		};

单元测试

string seq;
		TEST_METHOD(TestMethod1)
		{
			seq = "(())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod11)
		{
			seq = "(()())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			seq = "()(())()";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, res);
		}

栈

如果用栈判断一个字符串是否是合法括号

左括号入栈。遇到右括号，消掉栈顶的左括号，如果栈为空则非法。最终栈顶应该为空，否则非法。
a,b两个栈分别记录两个子序列，遇到左括号，放到元素少的栈。遇到右括号，消除栈顶元素多的栈。
我们只需要知道栈的元素数量，故可以ca，cb记录两者的数量。
时间复杂度：O(n)

代码

class Solution {
		public:
			vector<int> maxDepthAfterSplit(string seq) {
				int ca = 0,cb=0;
				const int N = seq.length();
				vector<int> ret(N);
				for (int i = 0; i < N;i++ ) {
					if ('(' == seq[i]) {
						if (ca < cb) {
							ca++;
							ret[i] = 0;
						}
						else {
							cb++;
							ret[i] = 1;
						}
					}
					else {
						if (ca > cb) {
							ca--;
							ret[i] = 0;
						}
						else {
							cb--;
							ret[i] = 1;
						}
					}
				}
				return ret;
			}
		};

单元测试

		int MaxDeq(const string& s) {
			int ret = 0,cur=0;
			for (const auto& ch : s)
			{
				cur += ('(' == ch) ? 1 : -1;
				ret = max(ret, cur);
			}
			return ret;
		}
		int Res(const string& s, const vector<int>& res) {
			string s1, s2;
			for (int i = 0; i < s.length(); i++) {
				if (res[i]) {
					s1 += s[i];
				}
				else {
					s2 += s[i];
				}
			}
			return max(MaxDeq(s1), MaxDeq(s2));
		}
		string seq;
		TEST_METHOD(TestMethod1)
		{
			seq = "(())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, Res(seq, res));
		}
		TEST_METHOD(TestMethod11)
		{
			seq = "(()())";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, Res(seq, res));
		}
		TEST_METHOD(TestMethod12)
		{
			seq = "()(())()";
			auto res = Solution().maxDepthAfterSplit(seq);
			AssertEx(1, Res(seq, res));
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。