17. 动态规划十题（一道困难题）
17. 动态规划十题（一道困难题）
如果没学过动态规划，可以看本人之前写的动态规划文章学习（）本篇文章只是用于作为一个hot100题解集使用
-
简单而经典的dp题目，同时也约等于斐波那契数列
class Solution: def climbStairs(self, n: int) -> int: # dp[i]表示刚好停在第i阶的方案数，因此递推式为：dp[i] = dp[i-1] + dp[i-2] # 因此需要初始化dp[0]和dp[1]，显然dp[1]为1，dp[2]为2，为了正常递推，所以dp[0]为1； # 事实上dp[0]这个量没有意义，因为dp[0]表示刚好停在第0阶的方案，因此我们从dp[2]反推回去即可， # 不过设置这样一个dp[0]相当于设置了一个dummy结点，从而保证了n=1的情况也能正常运行而不用额外剪枝。 dp = [1] * (n + 1) for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[-1] -
本题不难，但是要注意res的形状如何生成以及初始化。
class Solution: def generate(self, numRows: int) -> List[List[int]]: res = [[1] * (i + 1) for i in range(numRows)] # 生成结果的基本形状！同时能够涵盖numRows为0和1的情况，以及不用再初始化那些为1的部分了 for i in range(2, numRows): # 行索引i，相当于第i+1行，该行有i+1个元素 for j in range(1, i): # 列索引j，每一行只需要更新从除去首尾之外的列索引 res[i][j] = res[i-1][j-1] + res[i-1][j] return res -
class Solution: def rob(self, nums: List[int]) -> int: # dp[i]表示沿街偷到房屋索引i-1（索引i-1不一定被偷）的时候，能偷到的最高金额 # 因此有递推式：dp[i] = max(dp[i-2] + nums[i-1], dp[i-1]) # 因此初始化dp[1]必为房屋索引0的金额，dp[0]由dp[2]反推知必为0（dp[0]是用于简化讨论的） n = len(nums) dp = [0] * (n + 1) dp[1] = nums[0] for i in range(2, n + 1): dp[i] = max(dp[i-2] + nums[i-1], dp[i-1]) return dp[-1] -
这是一个完全背包问题（每种物品可以选 无限次），是求最优方案而不是求方案有几个，
非排列组合问题所以石头和背包容量的内外层顺序不重要
（可以参看动态规划 15. 组合总和 Ⅳ（完全背包问题中组合和排列问题的不同遍历顺序详解）_完全背包组合-CSDN博客，如果不理解为什么内外顺序会影响结果，可以直接该文章拉到最后看gpt对不同内外顺序的模拟！）
二维dp方法：
class Solution: def numSquares(self, n: int) -> int: # 这是一个背包问题 # 获取0~n的完全平方数，同时也对应着他们各自的重量 weights = [i ** 2 for i in range(0, n + 1) if i ** 2 <= n] # 特别注意：石头重量最大也只需要达到最大背包容量n即可！否则会多出很多不必要的计算和石头选择！这是二维dp时间优化的关键 # dp[i][j]表示背包容量为j，用当前可使用的备选重量装（0~i索引的对应石头），最少能用多少个石头（数的重量）装满。 # 递推式：dp[i][j] = min(dp[i-1][j], dp[i][j - weights[i]] + 1) # 表示dp[i][j]要么来自于不用石头i仅用前一轮用0~(i-1)索引的石头装满的方案，要么来自于当前轮用0~i索引的石头装满了j-weights[i]的容量然后再多装一个索引i的石头的方案。 dp = [[0] * (n + 1) for _ in range(len(weights))] # inf表示不可能装满 # 由于递推式要用到左上和左边的数据，所以要从左到右从上到下更新，且需要初始化行0、列0 # 列0表示要装满背包容量0，所以必然只需要0个石头 # 行0表示要用索引0石头也就是重量0的石头装满背包，所以除了背包容量0的情况，其他都不可能装满，所以初始化为inf for j in range(1, n + 1): dp[0][j] = inf for i in range(1, len(weights)): # 注意这里石头索引i的范围！ for j in range(1, n + 1): # 背包容量j小于索引i石头的重量时，不能添加石头i，所以必须要进行一个判断，且该种情况下，dp[i][j]的方案必然来自于dp[i-1][j] if j < weights[i]: dp[i][j] = dp[i-1][j] else: dp[i][j] = min(dp[i-1][j], dp[i][j - weights[i]] + 1) return dp[-1][-1]理解了二维dp就可以将空间优化到一维dp了！
class Solution: def numSquares(self, n: int) -> int: weights = [i ** 2 for i in range(n + 1) if i ** 2 <= n] w_len = len(weights) # 候选石头的总个数 # dp[j]表示，用当前能用的石头装背包，装满背包容量j最少要几个石头 # 当前的初始化相当于二维dp的行0初始化，背包容量0时为0，背包容量超过0时不可能装满所以为inf dp = [inf] * (n + 1) dp[0] = 0 for i in range(1, w_len): # i从0开始其实也可以，因为我们已经初始化了行0，对于dp[0][j]且j大于0的情况，必然是在dp[j]和dp[j] + 1中间取最小，依然是inf，不会错误覆盖 for j in range(weights[i], n + 1): # 注意这里j要从石头i的重量开始向右更新，因为更小的j没法使用石头i，跳过这些情况相当于直接拷贝上一层的方案了 dp[j] = min(dp[j], dp[j - weights[i]] + 1) return dp[-1] -
和前一道题基本一模一样
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # 硬币索引i -> 石头索引i，硬币面额coins[i] -> 石头重量，总金额 -> 背包容量 # 同一硬币可取任意次 -> 完全背包问题 # 求装满背包的最少石头个数 -> 求最优方案，而非排列组合 w_len = len(coins) # 可选石头数量 # dp[j] 表示使用当前可用石头（索引0~i，i最大为w_len - 1）装满背包容量j，所需最少石头数量 # 初始化dp，相当于初始化对应二维dp表的行0，即不能使用任何石头，等价于用石头重量为0，去装背包 dp = [inf] * (amount + 1) # 背包容量0 ~ amount dp[0] = 0 for i in range(w_len): for j in range(coins[i], amount + 1): # 注意新一行的背包容量要从石头i的重量开始更新 dp[j] = min(dp[j], dp[j - coins[i]] + 1) return dp[-1] if dp[-1] != inf else -1 # 注意本题中，可能出现无可行方案的情况！ -
完全背包 + 排列问题
相当于先从上到下再从左到右遍历（想象一个二维的dp表格，行为物品，列为背包）
每一次外循环，相当于固定背包，然后选或不选当前的新物品追加在之前已计算过的更小背包容量的方案之后，获得一个对于当前背包的最优方案
新物品必须能装得进背包才能对其进行取或不取二选一操作（即同时获取左边和上方的方案取最优），否则就是直接拷贝已有的相同背包容量方案（即直接拷贝上方的方案）
class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: # 字符串s -> 目标背包容量，wordDict中的元素 -> 石头重量 # 可以重复使用石头 -> 完全背包 # 选择石头的前后顺序会影响组成的字符串，所以是排列问题 w_len = len(wordDict) # 候选石头数量 s_len = len(s) # dp[j] 表示长度为j的字符串s[:j]（背包容量），是否能由当前可用的单词（石头重量）拼出（装满） # 初始化dp相当于初始化二维dp的行0，此时不用任何单词，因此j为0时dp为True，j大于0时dp为False # 递推式：dp[j]的方案要么来源于上一行的j长度方案，要么来源于当前行左边j-len(wordDict[i])长度的方案然后附上一个新的石头i dp = [False] * (s_len + 1) # j的范围为0 ~ s_len dp[0] = True # 排列问题，需要外背包内石头，因为固定背包遍历石头才能取出不同的石头顺序 for j in range(0, s_len + 1): # 目标字串长度j从0 ~ s_len for i in range(w_len): # 固定目标字串长度j，从上到下遍历所有石头 word = wordDict[i] # 当前侯选石头 if j < len(word): # 此时不可能选中该石头，必然是False continue # 两种方案其中一个成立就可以，所以用or连接 dp[j] = dp[j] or (dp[j - len(word)] and s[j-len(word):j] == word) return dp[-1] -
经典子序列问题，LIS没有“容量”或“价值”，也不是“选/不选”，而是“找最长合法顺序”，所以不是01背包。
这里dp不能看成二维dp表格，而是想象成一行dp，从左到右遍历dp，每次都要从当前列左侧所有列获取信息。
dp解法：
时间复杂度O(n^2)
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: # 经典子序列问题，LIS没有“容量”或“价值”，也不是“选/不选”，而是“找最长合法顺序”，所以不是01背包 # 这里dp不能看成二维dp表格，而是想象成一行dp，从左到右遍历dp，每次都要从当前列左侧所有列获取信息。 # dp[j]表示必须以nums[j]结尾的最长严格递增子序列的长度 # dp[j]的来源为其左侧的所有子序列，也就是在0~j-1范围内的索引i的dp，只要i处的num小于j处的num，说明当前dp[j]可以在dp[i]的子序列基础上添加上j处num（也就是dp[i] + 1） # 固定j，遍历j左侧的所有i，即可找到最长的符合要求的以j结尾的子序列。 # dp初始化为1，因为以j结尾的所求子序列，长度最短也是1，因为总是可以取自身（不过列0的元素长度最长为1） n = len(nums) dp = [1] * n # 额外使用ans来维护遇到过的最长所求子序列长度 ans = 0 for j in range(n): for i in range(j): # 遍历j左侧的所有最优方案 if nums[i] < nums[j]: dp[j] = max(dp[j], dp[i] + 1) ans = max(ans, dp[j]) return ans
二分查找解法：
更快， 时间复杂度O(nlogn)
- 每次只执行一次二分查找 →
O(log n) - 总共执行
n 次二分查找 →n * log n
二分查找O(n)空间版本：
常用
bisect函数：-
bisect.bisect_left(a, x)
返回数组a 中第一个 ≥x 的位置（插入位置） -
bisect.bisect_right(a, x)
返回数组a 中第一个 >x 的位置（右插入点） -
bisect.insort_left(a, x)
将x 插入到a 中，保持有序（用的是bisect_left）
import bisect # 引入 bisect 模块，用于二分查找插入位置 def lengthOfLIS(nums): tails = [] # tails[i] 表示长度为 i+1 的递增子序列的最小结尾元素 for x in nums: # 遍历每个数字 # 在 tails 中找第一个大于等于 x 的位置（即 x 可以接在的最短递增子序列末尾） i = bisect.bisect_left(tails, x) if i == len(tails): # 如果 x 比 tails 所有元素都大，说明可以接在最长序列后面 # 增加 tails 长度，代表找到更长的递增子序列 tails.append(x) else: # 否则，用 x 替换 tails[i] # 这样做是为了让 tails[i] 尽可能小，便于后续接更大的数 tails[i] = x # tails 的长度即为最长递增子序列的长度 return len(tails)如果要自己写二分查找函数的话：
class Solution: def findLowerBound(self, nums, target): # 找到nums中第一个大于等于target的索引，所以right及其右边必须要大于等于target # 二分查找，开区间写法(left, right) left = -1 right = len(nums) while left + 1 < right: # 区间非空 mid = (left + right + 1) // 2 if nums[mid] < target: # left及其左边一定小于target left = mid else: # right及其右边一定大于等于target right = mid return right # 所以right必然落在第一个大于等于target的索引上 def lengthOfLIS(self, nums: List[int]) -> int: tails = [] for x in nums: firstBigger = self.findLowerBound(tails, x) # 找到tails中第一个大于等于x的索引 if firstBigger == len(tails): tails.append(x) else: tails[firstBigger] = x return len(tails)
二分查找O(1)空间版本：
节省了额外的空间开销，直接复用了
nums 数组的前缀来充当tails 数组其中
bisect_left(nums, x, 0, ng) ：- 表示在
nums[0:ng] 这个区间中，找第一个 ≥x 的位置（也就是tails 数组中的二分查找） - 注意：我们虽然在
nums 中找，但只看前ng 项
bisect.bisect_left(a, x, lo=0, hi=len(a))用法：参数名 含义 a要进行二分查找的有序数组（这里是 nums） x要查找的位置（目标值） lo查找起点索引，默认是 0（这里明确写成 0） hi查找终点索引（不包含），默认是 len(a)（这里是ng）import bisect class Solution: def lengthOfLIS(self, nums: List[int]) -> int: ng = 0 # g 数组的有效长度，等价于 tails 数组长度 for x in nums: j = bisect.bisect_left(nums, x, 0, ng) # 在 nums[0:ng] 中找 >=x 的最左位置 nums[j] = x # 覆盖位置 j，相当于更新 tails[j] if j == ng: ng += 1 # 新增一个长度 return ng
给出gpt对该解法的讲解，比较清晰易懂：
🧠 一、贪心 + 二分法解 LIS 的核心思想
我们维护一个数组
tails，其中：-
tails[i] 表示：长度为i+1 的递增子序列的最小结尾元素
🚩 为什么这么做？
- 我们不关心完整的子序列内容；
- 只要知道：长度为
i+1 的子序列，我们用最小的结尾值留出最大空间给后面接更大的数。
👇 算法步骤：
遍历
nums 中的每个数x，对每个x：- 用 二分查找，找出
tails 中第一个 ≥x 的位置i - 如果没有找到（说明
x 比所有tails 中的数都大），就append(x)（表示子序列长度+1） - 否则，用
x 替换tails[i]（更小的结尾更有潜力延长）
✅ 代码实现（贪心 + 二分）：
import bisect def lengthOfLIS(nums): tails = [] for x in nums: i = bisect.bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails)
🧪 示例演示
以
nums = [10, 9, 2, 5, 1, 2, 3, 7, 101, 18, 8] 为例，一步步演示使用贪心 + 二分法 解决最长递增子序列（LIS）的过程。初始：
tails = []i 当前数 x bisect_left(tails, x)操作 tails更新后0 10 0 append [10] 1 9 0 替换 [9] 2 2 0 替换 [2] 3 5 1 append [2, 5] 4 1 0 替换 [1, 5] 5 2 1 替换 [1, 2] 6 3 2 append [1, 2, 3] 7 7 3 append [1, 2, 3, 7] 8 101 4 append [1, 2, 3, 7, 101] ✅ 9 18 4 替换 [1, 2, 3, 7, 18] 10 8 4 替换 [1, 2, 3, 7, 8] ✅ 最终结果：
-
tails = [1, 2, 3, 7, 8] - 长度为 5，即最长递增子序列的长度是 5
- 每次只执行一次二分查找 →
-
又是一道新的题型。dp的题目真是没做过就是想不出来啊！
常规dp法：
这道题的重要思路是，要同时维护两组dp，一个要维护最大乘积，一个要维护最小乘积
当前dp[j]（不管是最大乘积dp还是最小乘积dp）的来源都是下面三个，只是对应的三者取一的逻辑不同：
- 取以 j-1 结尾的非空连续子数组的最大乘积，然后乘上 j 处的数
- 取以 j-1 结尾的非空连续子数组的最小乘积，然后乘上 j 处的数
- 单取 j 处的数
class Solution: def maxProduct(self, nums: List[int]) -> int: # dp_max[j]表示以nums[j]结尾的非空连续子数组对应的最大乘积 # dp_min[j]表示以nums[j]结尾的非空连续子数组对应的最小乘积 # 由于是非空连续子数组，所以两者的可能来源均如下： # 1. 取以j-1结尾的非空连续子数组的最大乘积，然后乘上j处的数 # 2. 取以j-1结尾的非空连续子数组的最小乘积，然后乘上j处的数 # 3. 单取j处的数 # 最大乘积必为三者中最大者，最小乘积必为三者中最小者 # 想象一下，两数分别乘上一个正数不会改变大小关系，分别乘上一个负数会翻转大小关系； # 所以，如果j处是正数，那么j处的最大乘积必然是1、3中其一，j处的最小乘积必然是2、3中其一；如果j处是负数，那么j处的最大乘积必然是2、3中其一，j处的最小乘积必然是1、3中其一。 # 合并情况就是：最大乘积必为1、2、3中最大者，最小乘积必为1、2、3中最小者 n = len(nums) dp_max = [0] * n dp_min = [0] * n dp_max[0] = dp_min[0] = ans = nums[0] # 以0处结尾的非空连续子数组最大乘积和最小乘积必为其自身，同时维护一个最大乘积ans for j in range(1, n): num = nums[j] dp_max[j] = max(dp_max[j-1] * num, dp_min[j-1] * num, num) dp_min[j] = min(dp_max[j-1] * num, dp_min[j-1] * num, num) ans = max(ans, dp_max[j]) return ans写出了上面的代码，滚动计算空间优化就容易写了：
class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) dp_max = dp_min = ans = nums[0] # 以0处结尾的非空连续子数组最大乘积和最小乘积必为其自身，同时维护一个最大乘积ans for j in range(1, n): num = nums[j] source1, source2 = dp_max * num, dp_min * num # 提前保存，防止数据被更改影响三取一 dp_max = max(source1, source2, num) dp_min = min(source1, source2, num) ans = max(ans, dp_max) return ans当然也可以如下这么写：
python多变量赋值会先同时计算右侧所有表达式的值，再一次性赋值给左边变量，
也就不用担心值被覆盖的问题：
class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) dp_max = dp_min = ans = nums[0] # 以0处结尾的非空连续子数组最大乘积和最小乘积必为其自身，同时维护一个最大乘积ans for j in range(1, n): num = nums[j] dp_max, dp_min = max(dp_max * num, dp_min * num, num),\ min(dp_max * num, dp_min * num, num) ans = max(ans, dp_max) return ans -
一维dp，直接递推能否成功恰好装满背包：
本题实际上是从nums的石头中选石头，石头重量为nums中的num，且每个石头最多只能取一次（也就是取或不取），那就是01背包。
我们需要查看是否能刚好装满背包容量target（重量总和的一半），那么剩下的石头必然属于另一半子集。
dp[j]（实际上可以想象一个二维dp表格dp[i][j]）表示当前可选可不选石头i，能否找到方案装满背包容量j（其中石头0~i-1的方案已经计算过了）
所以dp[j]的来源如下：
- 不取当前石头i，那么方案可不可行由上方的方案决定（也就是i-1行的背包j方案），
dp[j]（或者说dp[i-1][j]） - 取当前石头i，那么方案可不可行由左上方也就是i-1行剩余背包容量j-nums[i]对应的方案决定，
dp[j-nums[i]]（或者说dp[i-1][j-nums[i]]
两来源以or逻辑连接
注意背包容量j小于石头i时，石头i必不可选，直接拷贝上一行信息即可；
注意由于我们需要用到上方和左上方的信息，且我们写的是一维dp，
所以如果我们j的遍历从左到右，会导致左边的dp信息被覆盖，而产生错误递推，
因此j的遍历必须从右向左遍历！
dp的初始化：初始化不用任何石头，也就是石头重量为0，那么除了j为0时为True，剩下的j必然都为False
class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2 == 1: # 剪枝，总和为奇数时必然不可能分成两份 return False target = sum(nums) // 2 # 目标和 # dp的初始化：初始化不用任何石头，也就是石头重量为0，那么除了j为0时为True，剩下的j必然都为False dp = [False] * (target + 1) dp[0] = True for num in nums: # 遍历石头 for j in range(target, num - 1, -1): # 倒序遍历背包容量，注意背包容量只在大于等于num时更新 dp[j] = dp[j] or dp[j - num] # 不选num 或者选num if dp[-1] == True: return True # 剪枝，每多经过一个石头选项，就检测一次，只要能成功就退出 return False也可以这样写：
递推最大化当前背包内重量，相当于最大化了target容量能装入的重量，若装入的重量刚好为target，说明方案成功了
class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2 == 1: # 剪枝，总和为奇数时必然不可能分成两份 return False target = sum(nums) // 2 # 目标和 # dp[j]（实际上可以想象一个二维dp表格dp[i][j]）表示当前可选可不选石头i，可以在背包容量j（其中石头0~i-1的方案已经计算过了）下装得的最大重量 dp = [0] * (target + 1) for num in nums: # 遍历石头 for j in range(target, num - 1, -1): # 倒序遍历背包容量，注意背包容量只在大于等于num时更新，这样能保证在j比num小的时候不被访问、更新到索引j-num（此时为负数，非法索引），从而使得背包容量j最多只能装入重量j！ dp[j] = max(dp[j], dp[j-num] + num) # 不选num 或者选num，能够得到的最大重量 if dp[-1] == target: return True # 剪枝，每多经过一个石头选项，就检测一次，只要能成功就退出 return False - 不取当前石头i，那么方案可不可行由上方的方案决定（也就是i-1行的背包j方案），
-
困难题
方法一：栈 + 跳跃问题
先利用栈获取所有合法左括号、右括号的索引对，看作一个跳跃的映射，记录在哈希字典中；
然后将问题转化为跳跃问题：若当前索引在字典的key中，则触发跳跃；否则步进寻找下一个合法起跳点。
由于从左到右遍历s，所以若触发跳跃，必然是从一个最外层的合法左括号跳到合法右括号！
因此我们可以继续查看下一个括号是否是合法起跳点（合法左括号），是的话继续当作当前区间进行跳跃，否的话直接重置区间。
class Solution: def longestValidParentheses(self, s: str) -> int: # 先获取合法的对应左括号索引->右括号索引映射，如"((())"含有的合法映射为1->4, 2->3 # 这可以看作一种跳跃！ # 然后按照跳跃问题来处理，通过跳跃，获取最长的连续区间 stack = [] # 栈，存储当前遇到的左括号的索引 left2right = {} for i, char in enumerate(s): if char == "(": # 遇到左括号，将索引入栈 stack.append(i) continue # 遇到右括号，如果stack非空，说明有对应的合法映射出现了！若为空则跳过 if stack: left2right[stack.pop()] = i # 左括号索引 -> 右括号索引 # 接下来再次遍历s，获取最长连续有效字串长度 ans = 0 # 最长长度 start = 0 # 当前连续有效字串的起始索引 end = 0 # 当前连续有效字串的终止索引，同时也是当前指针（当前有效字串区间为左闭右开[start, end)） while end < len(s): if end not in left2right: # 当前是右括号或者不合法的左括号 end += 1 # 指针步进 start = end # start重置 else: # 当前是合法的左括号，维持start，开始跳跃 end = left2right[end] + 1 # 指针指向下一个不确定是否合法的左括号 ans = max(ans, end - start) # 合法跳转时立即更新ans，非法符号上不需要更新，因为必然为0 return ans方法二：索引栈
上一个方法思路比较直接，但是有优化的空间，我们不需要先遍历一遍获取所有合法跳跃的映射，而是可以通过索引栈直接一次遍历就解决这个问题。
思路：
-
使用一个栈存放未匹配的
'(' 的索引； -
每当遇到一个
')' 并且可以配对，就尝试计算当前合法区间长度； -
如果不能配对，则记录此
')' 的位置，作为之后区间的起点参考； -
关键点在于区间左边界怎么取：
- 栈非空 → 从栈顶索引之后开始；
- 栈空 → 从上一个 unmatched
')'（last_invalid）之后开始；
class Solution: def longestValidParentheses(self, s: str) -> int: stack = [] # 栈，只在遇到左括号时入栈！存储当前遇到的左括号的索引，并与后序右括号匹配 ans = 0 # 最长长度 last_invalid = -1 # 最近一个无法匹配的右括号 ')' 的索引，用来恢复一个大区间，例如"()()"走到索引2和4的时候 for i, char in enumerate(s): if char == "(": # 遇到左括号，将索引入栈 stack.append(i) continue # 遇到右括号，如果stack非空，说明有对应的合法映射出现了！若为空则作为新的不匹配的右括号索引更新 if stack: stack.pop() # 当前pop出来的左括号索引与当前遇到的右括号匹配 if stack: # pop后stack非空，则此时stack栈顶的左括号索引的右侧为当前区间的出发点 start = stack[-1] else: # pop后stack为空，则此时上一个遇到的不匹配的右括号索引的右侧为当前区间的出发点 start = last_invalid ans = max(ans, i - start) # 注意有效区间为(start, i]，不包含start！ else: # stack为空，当前索引为最新的不匹配的右括号索引，相当于需要重置区间了 last_invalid = i return ans另一种针对方法一的优化，大致思路相同，但是具体细节有区别：
思路：
-
使用一个栈
stack 存放括号的索引（不是字符），用于判断是否构成有效括号； -
初始将
-1 压入栈，作为最初合法子串的起点（这是“哨兵值”）； -
遍历字符串：
-
遇到
'('：将其索引入栈； -
遇到
')'：-
如果栈顶可以配对
'('，就弹出它，然后计算当前合法子串长度； -
如果栈变空（说明没有匹配的
'(' 了），将当前索引作为新的起点压入栈。注意：
这里虽然右括号的索引会入栈，
但是实际上连续的不匹配的右括号只会一直
栈pop -> 栈空 -> 当前不匹配的右括号索引入栈，所以直到找到了新的左括号入栈之前，栈都只会记录最新的不匹配右括号索引，
这就相当于将前一种优化中的
last_invalid放入了栈中！
-
-
为什么需要哨兵
-1 ？举个例子：
s = "()" # 有效子串长度 = 2遍历完后，我们需要做：
length = i - stack[-1] = 1 - (-1) = 2若没有
-1 ，会怎样？- 初始栈为空；
- 第一个
')' 弹出'(' 后栈就空了； - 没有任何东西可以作为“合法区间起点”，你就无法正确计算长度！
class Solution: def longestValidParentheses(self, s: str) -> int: stack = [-1] # 初始栈中放一个哨兵 -1 max_len = 0 for i, ch in enumerate(s): if ch == '(': stack.append(i) # 记录左括号的位置 else: stack.pop() # 匹配最近的 '(' if not stack: stack.append(i) # 如果栈空了，说明当前 ')' 没有匹配的 '('，放新起点 else: max_len = max(max_len, i - stack[-1]) # 匹配成功，更新最大长度 return max_len方法三：动态规划（由gpt生成）（个人认为dp方法很绕，不如前面的做法好）
数组
dp[i] 表示：- 以 s[i] 结尾的最长有效括号子串的长度（很重要，想不出dp的定义，就没法用dp正确做出！）
状态转移方程：
-
我们只关心当
s[i] == ')' 时的情况，因为有效括号必须以右括号结尾（以左括号结尾的索引对应dp值都为0！）。设当前位置为
i：-
情况 1：
s[i-1] == '('这构成
...()，只需要前面dp[i-2] 的长度：dp[i] = dp[i-2] + 2如果 i-2 处是左括号，则 dp[i] 为2；如果 i-2处是右括号，则 dp[i] 相当于在 dp[i-2]长度的基础上加了两个字符的长度。
-
情况 2：
s[i-1] == ')'这构成
...))，我们就要看能否找到和s[i] 配对的左括号：由于 i-1 处也是右括号，所以dp[i-1] 表示以 i-1 结尾的最长连续有效字串的长度，
所以
i - 1 - dp[i-1] 指向了以 i-1 结尾的最长连续有效字串的开头的左侧一格！因此查看
i - dp[i-1] - 1 是否是 '(' ：-
如果此处是左括号， 相当于构成了
...((...))，说明该处左括号与 i 处右括号相匹配了，也就是说，dp[i] 相当于在 以 i-1 结尾的最长连续有效字串 前后各加上了长度1（前面加了一个左括号
i - dp[i-1] - 1，后面加了一个右括号i）因此至少
dp[i] = dp[i-1] + 2-
如果
i - dp[i-1] - 2处还大于等于0，那么i - dp[i-1] - 2处的dp可能也会带来额外的有效串，并与dp[i]相连，所以此时我们还要加上
i - dp[i-1] - 2处的dp：dp[i] += dp[i - dp[i - 1] - 2]
-
-
如果此处是右括号，相当于构成了
...)(...))，由于
[i - dp[i - 1], i - 1]这个区间已经是最长的以 i - 1 结尾的合法连续字串了，所以说明此时 i 处的右括号是不匹配的右括号，因此直接跳过，保留原来的dp值0。可以以
")(()))"为例手动模拟
-
-
完整代码：
class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) dp = [0] * n # dp[i] 表示以 s[i] 结尾的最长有效子串长度 max_len = 0 for i in range(1, n): if s[i] == ')': if s[i - 1] == '(': # 情况 1：() -> dp[i] = dp[i-2] + 2 dp[i] = (dp[i - 2] if i >= 2 else 0) + 2 elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(': # 情况 2：...))，且前面能配对的 ( dp[i] = dp[i - 1] + 2 if i - dp[i - 1] - 2 >= 0: dp[i] += dp[i - dp[i - 1] - 2] max_len = max(max_len, dp[i]) # 更新最大值 return max_len -
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
30
0- 0
已为社区贡献5条内容
所有评论(0)