- 首先来一个题目：leetcode 32. 最长有效括号
问题：在一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 "()()"
范围：
0 <= s.length <= 3 * 10^4，其中s[i] 为 '(' 或 ')'。
动态规划思路
- 初见动态规划可能会觉得无从入手，这里我们将动态规划分为三点：状态，边界，转移。
状态
状态是指题目的条件能够组成的所有可能结果（比如括号的数量，每个括号是左括号还是右括号，括号的配对方式等）。
由于状态的描述方式许多，多数描述跟题目无关，这里给出一个固定句式：
在 <满足问题的条件> 下，<问题的最佳答案> 就是状态。
此题中，代入句式得到：在<长度为s.length条件>下，《最长有效括号子串的数量《就是状态。
观察句式，句式中的变量只有长度，我们修改长度的表述，可以得到 <长度为1下>，《最长有效括号子串的数量》；<长度为2下>，《最长有效括号子串的数量》··· 等等表述。显然这些表述组合起来就是一个一维数组，通常习惯将此数组命名为dp。
正式地：
● 设在<长度为i条件下>，《最长有效括号子串的数量》就是dp[i]。
● dp就是状态数组。
边界
在固定句式中，代入确切的初始条件和终止条件，就是我们的边界，也是思考的起点和终点。
此题中的所有状态：<长度为1下>，《最长有效括号子串的数量》；<长度为2下>，《最长有效括号子串的数量》···
- 初始条件<长度为1下>的情况是容易计算的，显然<长度为1下>，《最长有效括号子串的数量》是0，那么得到dp[1]=0。
- 再有终止条件：在<长度为s.length条件>下，《最长有效括号子串的数量》就是dp[s.length]，也就是题目的答案。
dp[1] = 0;
answer = dp[s.length];
转移
转移是由已知状态推导未知状态的过程。具体地讲：
Q：什么是已知未知？
A：在边界中，dp[1]=0就是已知状态，所求的答案dp[s.length]就是未知状态。
Q：转移是如何操作的？
A：根据已知推未知，逐步推导。
示例：字符串 s = “)()())”
第一个字符为 )， 同时已知状态dp[1]=0就表示<长度为1下>，《最长有效括号子串的数量》是0。
加入第二个字符，则目前为)(，通过已知状态dp[1]和已知第二个字符(来推导未知状态dp[2]。
以此类推 加入第三个字符，目前为)()，通过已知状态dp[2]和已知第三个字符)来推导未知状态dp[3]。
正式地：
通过已知状态dp[i-1]和已知第i个字符s[i]，来推导未知状态dp[i]。
简单表达：dp[i] = ( dp[i-1], s[i] )
Q：在计算 dp[i] 时，可以利用的信息有哪些？
A：只可利用dp[i-1], s[i-1], s[i] 等邻近 i 的数据。
详细说明：若在计算dp[i]时，使用了 dp[1], dp[2]···，那么本次计算就要访问i-1个元素。
根据上述，计算i=1时访问0个元素，计算i=2时访问1个元素···，计算i=n时访问n-1个元素。
则计算完 i=n 时已经访问了 0+1+2+···+n-1 = n^2 ，即时间复杂度为O(n^2)。
诸如dp[i] = ( dp[i-1], s[i] )的式子，称为状态转移方程。
解题步骤
1. 根据状态的固定句式，假设一个合理的状态，并说明答案和状态的关系。
2. 分类讨论每种状态对应的含义，写出状态转移方程。
3. 若第2步无法写出方程，则检查状态是否完备，并继续步骤1。
- Q: 如何检查状态设置的正确性？
a. 状态需要包含推导所需所有可能，不能有遗漏。
b. 状态i 和 之前的状态i-1, i-2···不能有交集。
本题示例：
- 使用上文设置的状态: dp[i]为在<长度为i条件下>，《最长有效括号子串的数量》，答案就是dp[n]。
- 思考状态转移方程，计算未知状态dp[i]时，已知dp[i-1]的值，对dp[i-1]的值分类讨论。
a. dp[i-1] 为0，则表示之前从未出现过有效的括号子串。
b. dp[i-1] 不为0，则表示之前出现过有效的括号子串，不知道在[1, i-1]的哪一段出现的。 - 这时我们发现使用dp[i-1]不大能够推算出dp[i]，因为dp[i-1]和dp[i]都包含了可能 在[1, i-1]的某一段出现了《最长有效括号子串的数量》，违背状态的正确性。
hint: 常在
固定句式中使用限定词“以i为结尾”
- 使用上文设置的状态: dp[i]为在<长度为i条件下>，《以i为结尾的最长有效括号子串的数量》。答案就是dp[1]到dp[n]中的最大值。
- 思考状态转移方程，计算未知状态dp[i]时，已知dp[i-1]的值，对dp[i-1]的值分类讨论。
a. dp[i-1] 为0，则表示i-1位置的符号不能跟前面的括号匹配。前i-1个字符可能是：*** * * (** ，若此时s[i] = ')'，则 dp[i] = 2。
也可能是： ( ) )，则 dp[i] = 0。
b. dp[i-1] 为k, k>0，则表示从i-1往前k个是恰好匹配的连续括号子串。
> 因为前面k个已经成功配对了，那么dp[i] 只能尝试跟 往前找第k+1个字符 配对，也就是 s[i-k]='('，且s[i]=')'时才能配对，dp[i] = dp[i-1] + 2。
可以得到一份代码：
class Solution {
public:
int dp[30000 + 10], pos;
int longestValidParentheses(string s) {
// 因为c++下标从0开始, 这里填充一个字符在开头使得下标从1开始.
s = "*" + s;
// 边界
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= s.length(); i++)
{
dp[i] = 0;
if (dp[i - 1] == 0)
{
// a.
if (s[i - 1] == '(' && s[i] == ')')
dp[i] = 2;
}
else
{
// b.
// pos就是往前找k+1个字符的位置
// 比如 i=10，dp[i-1]=4,表示[6,7,8,9] 是匹配的子串，则 pos=5
pos = i - dp[i - 1] - 1;
if (s[pos] == '(' && s[i] == ')')
dp[i] = dp[i - 1] + 2;
}
}
int ans = 0;
for (int i = 1; i <= s.length(); i++)
ans = max(ans, dp[i]);
return ans;
}
};
这里我们发现并不能解答此题，拿到错误数据为：")()())"，错误答案为2。
我们发现是5号位置计算错误，根据状态的定义：《以i为结尾的最长有效括号子串的数量》，dp[5]应该为4。
- 那么我们需要检查状态转移方程，发现无论是a. 还是b.，在i位置发生匹配时，就要注意是否前面也有一个完整的匹配，形如 * * * √ √ √ √ ( ) ，dp[i]的值应该为本次匹配的结果加上 上一个紧挨着的连续合法括号串长度（上一个紧挨着的位置是pos=i-dp[i]）。
- c. 第三条转移方程： 当i位置匹配成功（即dp[i]>0）时，也要加上 上一个紧挨着的连续合法括号串长度(即dp[pos])
// 代码如下
pos = i - dp[i];
if (dp[i])
dp[i] += dp[pos]
// pos的值带进来简写
if (dp[i])
dp[i] += dp[i - dp[i]]
最终代码
class Solution {
public:
int dp[30000 + 10];
int longestValidParentheses(string s) {
// 因为c++下标从0开始, 这里填充一个字符在开头使得下标从1开始.
s = "*" + s;
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= s.length(); i++)
{
dp[i] = 0;
if (dp[i - 1] == 0)
{
if (s[i - 1] == '(' && s[i] == ')')
dp[i] = 2;
}
else
{
int pre_pos = i - dp[i - 1] - 1;
if (s[pre_pos] == '(' && s[i] == ')')
dp[i] = dp[i - 1] + 2;
}
// c. 加这里
if (dp[i])
{
dp[i] += dp[i - dp[i]];
}
}
int ans = 0;
for (int i = 1; i <= s.length(); i++)
ans = max(ans, dp[i]);
return ans;
}
};
关于我们
欢迎关注公众号《奇迹狗狗》，很开心在这里能和你相遇~
我们会分享一些技术文章，包括但不限于游戏技术、云原生、ACM题解、基础编程知识等，如果能授人以渔，荣幸之至！
我们也会做一些有温度的产品、游戏，会陆续分享给大家，如果能博君一笑，再好不过！
产品列表：
★ WorkerHub小程序，信息均来自各个大厂员工爆料，可以查询各个公司/部门/岗位的工作做细、工作体验、工作评价等，供打工er找工作的时候参考，避雷卷王团队/天坑团队！
网友评论