LeetCode短视频 | 最长有效括号使用栈很容易解决，但偏用动态规划

约定不等于承诺〃 2023-06-20 10:54 2阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![format_png][]

今天分享的题目来源于 LeetCode 第 32 号问题：*最长有效括号*。可以使用 **栈** 来解决，但我们偏用 **动态规划** 看看解决的是什么样子：）

# 题目描述 #

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

**示例 1:**

输入: "(()"
    输出: 2
    解释: 最长有效括号子串为 "()"

**示例 2:**

输入: ")()())"
    输出: 4
    解释: 最长有效括号子串为 "()()"

# 题目解析 #

看了这个题目的标签，动态规划是其的标签之一。这题目我第一反应可以使用栈来解决，但我们偏用动态规划看看解决的是什么样子的。

我们定义一个dp\[i\]数组，其中i表示字符串的下标，值是目前有效的子字符串。

我们将dp数组全部初始化为0。

现在，很明显有效的子字符串一定以‘)’结尾。

我们可以进一步得出结论：以‘(’的子字符串对应位置上的值必定为0。

所以说我们只需要更新‘)’在dp数组中对应位置的值。

为了求出dp数组，我们每两个字符检查一次，如果满足如下条件

s\[i\]=‘)’且s\[i−1\]=‘(’，形如‘‘…()..."，可以推出：dp\[i\]=dp\[i−2\]+2

可以进行这样的转移，是因为结束部分的"()"是一个有效子字符串，并且将之前有效子字符串的长度增加了2。

s\[i\]=‘)’且s\[i−1\]=‘)’，也就是字符串形如‘‘...))..."，我们可以推出：

如果s\[i−dp\[i−1\]−1\]=‘(’，则dp\[i\]=dp\[i−1\]+dp\[i−dp\[i−1\]−2\]+2

这背后的原因是如果倒数第二个‘)’是一个有效子字符串的一部分（记为s），对于最后一个‘)’，如果它是一个更长子字符串的一部分，那么它一定有一个对应的‘(’，它的位置在倒数第二个‘)’所在的有效子字符串(s)的前面。

因此，如果子字符串s的前面恰好是‘(’，那么我们就用2加上s的长度（dp\[i−1\]）去更新dp\[i\]。

除此以外，我们也会把有效子字符串‘‘(,s,)"之前的有效子字符串的长度也加上，dp\[i−dp\[i−1\]−2\]。

# 动画描述 #

**注意：动画视频有音乐！！！**

# 代码实现 #

![format_png 1][]

![音符][format_png 2]

**有热门推荐????**

1.【程序员】[我们就必须承认：这个世界上，有很多问题，就是无解的][Link 1]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了！][Link 2]

![format_png 3][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFUN2tTdnJpYk9tQW5HeGpGczdaMWhTZjhrbjJQRUlrWTlwaWJWaWJraDZ0SW15WkdEdzZpYnhSNW9ibnZqVWliOXlRYkR6RHpvOWxNaHNhQS82NDA_d3hfZm10PWpwZWc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy95OHNTRUtOODJKbUNGRUVyME5OZ0tUTFJiV01oRjNTUXJaeW1OaWIwSWRSYU9qdU9SWWlhdFNDM1RuRFAxNHhPVHNpYkdOa2FnOU11aHZJSU5rdVhPV1BWQS82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6L2NaVjJoUnB1QVBpYUpRWFdHeUM5d3JVeklpY2liZ1hheXJnaWJUWWFyVDNBMXl6dHRidGFPMEpsVjIxd01xcm9HWVQzUXRQcTJDN0hNWXN2aWNTQjJwN2RUQmcvNjQwPw?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/100978627
[GitHub]: https://blog.csdn.net/kexuanxiu1163/article/details/100137152
[KMP]: https://blog.csdn.net/kexuanxiu1163/article/details/97071390
[Link 2]: https://blog.csdn.net/kexuanxiu1163/article/details/103051357
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVR1U2ljRUtJcWdpYU9FdG9KaWEwTGcxYTJkWkVLcXlwYzlFcDUzVkpsb0Vobzg4VkdYeVpFSHB2d1paVXR6VnR2RTVJRWliQU5kbFdwUVJRLzY0MD93eF9mbXQ9anBlZw?x-oss-process=image/format,png