LeetCode-Hot100-动态规划

前言

题单LeetCode 热题 100的动态规划部分，给出解析。

70. Climbing Stairs

题目描述

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

解题方法

这个爬楼梯问题可以分析为经典的动态规划问题：

问题分析：

到达第 n 级台阶的方法：

从 n - 1 级台阶走 1 步到达。
从 n - 2 级台阶走 2 步到达。

则到达第 n 级台阶的总方法数 f(n) 可以表示为前两级台阶的方法数之和：
$$
f(n) = f(n-1) + f(n-2)
$$
这个递推公式与斐波那契数列类似：
初始条件：
$f(1)=1$，只有一种方法到达第一级台阶；$f(2)=2$，有两种方法到达第二级台阶（一步一步走或者一步直接两级）。

代码实现

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        prev1, prev2 = 2, 1
        
        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        
        return prev1

变量解释：

prev1 表示前一级台阶的爬法数，prev2 表示前两级台阶的爬法数。
current 表示当前台阶的爬法数，根据公式，current = prev1 + prev2
prev2 = prev1：将 prev1 的值赋给 prev2，相当于在下一次迭代中，prev2 就代表了当前台阶的前两级台阶的爬法数。
prev1 = current：将 current 的值赋给 prev1，相当于在下一次迭代中，prev1 就代表了当前台阶的爬法数。
return prev1：当循环结束后，prev1 就表示爬到第 n 级台阶的总方法数，返回这个值作为最终结果。

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

118. Pascal’s Triangle

原题链接

题目描述

Given an integer numRows, return the first numRows of Pascal’s triangle .

In Pascal’s triangle , each number is the sum of the two numbers directly above it as shown:

Example 1:

1 2	Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

1 2	Input: numRows = 1 Output: [[1]]

Constraints:

1 <= numRows <= 30

解题方法

这个问题要求我们生成帕斯卡三角形的前 numRows 行。帕斯卡三角形的构造规则是，每个数字等于它正上方的两个数字之和，第一行和第二行都是由 1 组成的。

解题思路：

第一行：只有一个元素 1。
第二行：也是两个元素，都是 1。
从第三行开始：每个元素是上一行中相邻两个元素的和。比如第 i 行的第 j 个元素是 triangle[i-1][j-1] + triangle[i-1][j]，其中 triangle[i-1] 是上一行。
边界条件：每一行的第一个和最后一个元素都是 1。

解法：

我们可以通过循环构造每一行，然后把每一行添加到最终的结果中。

代码实现

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        triangle = []  # 存储 Pascal's 三角形
        for i in range(numRows):
            row = [1] * (i + 1)  # 创建当前行，并将所有元素初始化为 1
            for j in range(1, i):
                # 计算当前行除了第一个和最后一个位置之外的元素
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            triangle.append(row)  # 将当前行添加到 Pascal's 三角形中
        return triangle

复杂度分析

时间复杂度：$O(n^2)$，其中 $n$ 是 $numRows$。

空间复杂度：$O(1)$。

198. House Robber

原题链接

题目链接

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

解题方法

动态规划需要找到子问题，原问题是“从全部房子中能够偷到的最大金额”，子问题设为“从 k 个房子中能偷到的最大金额”，用 f(k) 表示。

子问题是参数化的，我们定义的子问题中有一个参数 k。如果有 n 个房子的话，一共有 n 个子问题。动态规划实际上是通过求这些子问题的解，来得出原问题的解。这些子问题需要具备两种性质：

原问题能够用子问题表示。
一个子问题的解能够用其他子问题的解求出。

状态转移方程：

对于每个房子有两种选择：

抢当前房子：那么最大金额应该是 dp[i-2] + nums[i]，即抢了当前房子后，再加上抢到 i-2 房子的最大金额。
不抢当前房子：那么最大金额应该是 dp[i-1]，即前一个房子抢到的最大金额。

综合以上两种情况，状态转移方程为： $$dp[i]=max⁡(dp[i−1],dp[i−2]+nums[i])$$
初始条件：

$dp[0] = nums[0]$：因为只有一个房子时，只能抢这个房子。
$dp[1] = max(nums[0], nums[1])$：只有两个房子时，选择抢金额较大的一个。

最终结果：返回 $dp[n-1]$。

代码实现

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 初始化dp数组
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n

        # 初始状态
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        # dp数组计算
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

        # 返回最终结果
        return dp[-1]

空间复杂度优化：

在上面的动态规划解法中，我们使用了一个长度为 n 的数组 dp 来存储每个房子抢劫到的最大金额。然而，我们注意到在计算 dp[i] 时，只需要用到 dp[i-1] 和 dp[i-2] 的值。因此，我们可以使用两个变量来替代整个数组，从而将空间复杂度优化为 $O(1)$。

优化思路：

我们只需要两个变量 prev1 和 prev2 来分别表示 dp[i-1] 和 dp[i-2]，然后逐步更新这两个变量即可。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        prev2 = nums[0]
        prev1 = max(nums[0],nums[1])

        for i in range(2, len(nums)):
            current = max(prev1, prev2 + nums[i])
            prev2 = prev1
            prev1 = current
            
        return prev1

代码解释：

特殊情况处理：如果只有一个房子，直接返回那间房子的金额。
初始化：prev2 代表 dp[i-2]，prev1 代表 dp[i-1]。
迭代更新：从第三个房子开始，计算当前房子的最大金额，然后更新 prev2 和 prev1。
返回结果：最后，prev1 中存储的就是抢劫到最后一个房子的最大金额。

复杂度分析

时间复杂度：仍然是 $O(n)$，因为我们需要遍历每一个房子。

空间复杂度：从 $O(n)$ 优化为 $O(1)$，只需要常量级的额外空间。

279. Perfect Squares

原题链接

题目描述

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

1
2
3

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 10^4

解题方法

动态规划

要解决这个问题，可以使用动态规划的方法。我们需要创建一个数组 dp，其中 dp[i] 表示求和为 i 所需的最小完全平方数的数量。

算法步骤：

初始化：创建一个大小为 n + 1 的数组 dp，并将所有元素初始化为 无穷大（或一个足够大的数），因为我们要寻找最小值。然后设置 dp[0] = 0，表示和为 0 时不需要任何数。
填充 dp 数组：对于每一个从 1 到 n 的数 i，遍历所有可能的完全平方数 j^2，并更新 dp[i]：
- 对于每个 i，我们检查所有小于等于 i 的完全平方数 j^2，其中 j 从 1 开始，直到 j^2 超过 i。
- 更新状态：dp[i] = min(dp[i], dp[i - j^2] + 1)。这里 dp[i - j^2] + 1 表示在和为 i - j^2 的基础上再加一个完全平方数 j^2。
返回结果：最终，dp[n] 即为答案。

BFS

BFS 可以用于从 n 开始，逐步减去所有可能的完全平方数，直到达到 0。每次减去一个完全平方数就记录一步，直到找到最短路径。

算法步骤：

预计算完全平方数：计算所有小于等于 n 的完全平方数。
使用队列进行 BFS：初始化一个队列，将 n 入队，记录步骤数。
遍历队列：每次从队列中取出一个数，检查减去每个完全平方数后的结果：
- 如果结果为 0，返回当前步骤数。
- 如果结果大于 0，继续入队。

数学定理

使用数学定理法，主要是依赖于Lagrange’s Four Square Theorem，该定理表明：任何正整数都可以表示为不超过四个完全平方数的和。这意味着我们只需检查一个数可以表示为多少个完全平方数的和，最多只需考虑 1 到 4 个平方数。

算法步骤：

检查特殊情况：
- 如果 n 是一个完全平方数，则直接返回 1。
- 检查 n 是否可以表示为两个完全平方数的和（可以用公式判断）。
- 如果 n 是 4 的某个幂次加上 3 的形式，则返回 4。
返回结果：
- 如果没有特殊情况，则最多返回 4。

代码实现

动态规划

class Solution:
    def numSquares(self, n: int) -> int:
        # 创建 dp 数组并初始化
        dp = [n + 1] * (n + 1)
        dp[0] = 0
        
        # 填充 dp 数组
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
                
        return dp[n]

BFS

class Solution:
    def numSquares(self, n: int) -> int:
        # 预计算小于等于 n 的完全平方数
        squares = []
        i = 1
        while i * i <= n:
            squares.append(i * i)
            i += 1
        
        # BFS 初始化，队列中放入 n
        queue = deque([n])
        level = 0  # 记录当前的步骤数
        
        while queue:
            level += 1  # 增加步骤数
            for _ in range(len(queue)):  # 当前层的元素个数
                current = queue.popleft()  # 从队列中取出当前数
                for square in squares:  # 遍历所有完全平方数
                    if current == square:  # 如果当前数等于完全平方数
                        return level  # 返回步骤数
                    if current < square:  # 如果当前数小于完全平方数，后面的不再检查
                        break
                    queue.append(current - square)  # 将减去平方数后的结果加入队列
        
        return level  # 返回步骤数（理论上不会执行到这里）

数学定理

class Solution:
    def numSquares(self, n: int) -> int:
        def is_square(x):
            """判断 x 是否是完全平方数"""
            s = int(math.sqrt(x))
            return s * s == x
        # 检查 n 是否是完全平方数
        if is_square(n):
            return 1
        
        # 检查 n 是否可以表示为两个完全平方数的和
        for i in range(int(math.sqrt(n)) + 1):
            if is_square(n - i * i):
                return 2
        
        # 检查 n 的形式是否为 4^k * (8m + 7)
        while n % 4 == 0:
            n //= 4
        if n % 8 == 7:
            return 4
        
        return 3  # 否则最多返回 3

复杂度分析

方法	时间复杂度	空间复杂度
动态规划	$O(n*√n)$，其中 n 是输入值。	$O(n)$，$dp$ 数组。
BFS	最坏情况下为 $O(n*√n)$。	$O(n)$，队列。
数学定理	$O(√n)$，主要用于判断是否为完全平方数。	$O(1)$，常量空间。

322. Coin Change

原题链接

题目描述

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

1
2
3

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

1 2	Input: coins = [2], amount = 3 Output: -1

Example 3:

1 2	Input: coins = [1], amount = 0 Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

解题方法

我们可以定义一个数组 dp，其中 dp[i] 表示组成金额 i 所需的最少硬币数量。我们的目标是找到 dp[amount] 的值。

具体步骤如下：

初始化 dp 数组，长度为 amount + 1，初始值都设为 amount + 1，因为这是不可能达到的最大值。唯一的例外是 dp[0]，其值为 0，因为组成金额 0 所需的硬币数量为 0。
遍历 dp 数组，从 1 到 amount。对于每个金额 i，检查每种硬币 coin，如果 i >= coin，则更新 dp[i]，更新的方式是 dp[i] = min(dp[i], dp[i - coin] + 1)。
最后，检查 dp[amount] 的值。如果 dp[amount] 仍然是初始值 amount + 1，说明无法组成该金额，返回 -1。否则，返回 dp[amount]。

代码实现

class Solution(object):
    def coinChange(self, coins, amount):
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], dp[i - coin] + 1)
        
        return dp[amount] if dp[amount] != amount + 1 else -1

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

139. Word Break

原题链接

题目描述

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

1
2
3

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

1 2	Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique .

解题方法

这个问题可以使用动态规划来解决。我们可以定义一个布尔数组 dp，其中 dp[i] 表示字符串 s 的前 i 个字符是否可以用字典中的单词进行分割。

思路：

初始化 dp 数组长度为 len(s) + 1，所有值初始化为 False。dp[0] 设为 True，因为空字符串可以被认为是被空的字典成功分割的。
遍历字符串 s 的每个位置 i，对于每个位置再遍历字典中的每个单词 word：
- 如果 word 的长度小于等于 i，并且 s[i-len(word):i] 等于 word，那么如果 dp[i-len(word)] 为 True，则将 dp[i] 设为 True。
最终，dp[len(s)] 的值即为结果，表示整个字符串是否可以被成功分割。

代码实现

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True

        for i in range(1, len(s) + 1):
            for word in wordDict:
                if i >= len(word) and dp[i - len(word)] and s[i - len(word):i] == word:
                    dp[i] = True
                    break
        
        return dp[len(s)]

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(n)$

300. Longest Increasing Subsequence

原题链接

题目描述

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

1
2
3

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

1 2	Input: nums = [0,1,0,3,2,3] Output: 4

Example 3:

1 2	Input: nums = [7,7,7,7,7,7,7] Output: 1

Constraints:

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

解题方法

定义一个 dp 数组，dp[i] 代表 nums 以 nums[i] 为结尾的最长递增子序列长度。

状态转移方程：

设 $j∈[0,i)$，即每一轮计算新的 $dp[i]$ 时，需要遍历 $[0,i)$ 列表区间
- 当 $nums[i] > nums[j]$ 时，表明 $nums[i]$ 可以接到递增序列的末尾，此时 $dp[i]=dp[j]+1$。
- $nums[i]<=nums[j]$ 时，跳过，因为此时 $nums[i]$ 不能够作为递增子序列的末尾。
- 转移方程：$dp[i]=max(dp[i],dp[j]+1),j∈[0,i),i∈[0,n]$
- 初始化 dp 为值为 1 的数组，因为每个元素都可以单独成为一个子序列。

改进：

将整个 dp 数组设计为一个排序列表，在需要计算最长递增子序列时，使用二分查找遍历 dp 数组，找到需要插入的下标位置，之后进行判断。

**初始化一个空的列表 sub**：
- 这个列表用于保存当前找到的最长递增子序列的末尾元素。
**遍历数组 nums**：
- 对于每个元素 num，使用二分查找来确定 num 在 sub 中的位置。
- 如果 num 大于 sub 中的所有元素（即 num 是新的最大值），就将其添加到 sub 的末尾。
- 如果 num 不是最大的，找到它在 sub 中应该插入的位置，并替换掉该位置的元素。这样可以保持 sub 的递增性质，并为后续元素提供更大的可能性。
返回 sub 的长度：
- sub 的长度即为最长严格递增子序列的长度。

代码实现

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

改进：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = []  # 用于保存当前找到的最长递增子序列的末尾元素

        def binary_search(target):
            left, right = 0, len(sub)  # 初始化左右指针
            while left < right:
                mid = (left + right) // 2  # 计算中间位置
                if sub[mid] < target:  # 如果中间元素小于目标值
                    left = mid + 1  # 继续在右半部分查找
                else:
                    right = mid  # 继续在左半部分查找
            return left  # 返回插入位置

        for num in nums:  # 遍历数组 nums
            pos = binary_search(num)  # 查找当前元素的插入位置
            if pos == len(sub):  # 如果插入位置等于 sub 的长度，说明是新的最大值
                sub.append(num)  # 添加到 sub 的末尾
            else:
                sub[pos] = num  # 否则替换掉当前位置的元素
                
        return len(sub)  # 返回 sub 的长度，即最长递增子序列的长度

复杂度分析

时间复杂度：$O(n^2)$到$O(nlogn)$。

空间复杂度：$O(n)$。

152. Maximum Product Subarray

原题链接

题目描述

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

1
2
3

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

解题方法

要找到一个整数数组 nums 中乘积最大的子数组，并返回这个最大乘积，我们可以使用动态规划的思路。这个问题的关键在于考虑负数对乘积的影响。

解决思路

初始化变量:
- 维护两个变量 max_product 和 min_product，分别表示当前遍历到的子数组中的最大乘积和最小乘积。
- 初始化 max_product 和 min_product 为数组的第一个元素，result 也初始化为第一个元素。
遍历数组:
- 对于数组中的每一个元素 num，我们需要考虑三种情况：
  1. num 本身。
  2. num 乘以前一步的 max_product。
  3. num 乘以前一步的 min_product。
- 因为乘以负数会导致最大值变成最小值，最小值变成最大值，所以我们需要同时更新 max_product 和 min_product。
- 更新 result，即记录遍历过程中遇到的最大乘积。
最终结果:
- 遍历结束后，result 中存储的即为最大子数组乘积。

代码实现

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 数组为空
        if not nums:
            return 0

        # 最大乘积
        max_product = nums[0]
        # 最小乘积
        min_product = nums[0]
        # 结果
        result = nums[0]

        # 遍历数组，从第二个元素开始更新 max_product 和 min_product
        for i in range(1, len(nums)):
            num = nums[i]
            
            # num < 0 会出现负数结果，交换最大乘积与最小乘积
            if num < 0:
                max_product, min_product = min_product, max_product
                
            max_product = max(num, max_product * num)
            min_product = min(num, min_product * num)

            result = max(result, max_product)

        return result

代码思想：

初始化 max_product, min_product 和 result 为数组的第一个元素。
遍历数组，从第二个元素开始更新 max_product 和 min_product。
每次更新 result 为当前最大值。
返回 result，即最大乘积的子数组的乘积。

复杂度分析

时间复杂度：$O(n)$

空间复杂度：$O(1)$

416. Partition Equal Subset Sum

原题链接

题目描述

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

1
2
3

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

解题方法

这道题是典型的「分割等和子集问题」，它可以通过动态规划（Dynamic Programming, DP）来解决。目标是将数组分成两个和相等的子集。如果数组的总和为奇数，则不可能进行这样的划分，因此可以直接返回 false。

解题思路：

数组总和为偶数：我们可以尝试找到一个子集，它的和等于总和 / 2。如果能找到这样的子集，说明剩余的元素和也是总和 / 2，问题就可以解决。
动态规划：我们用一个布尔数组dp来表示是否可以找到和为某个值的子集。dp[i]表示能否找到和为i的子集。初始时，dp[0] = true（表示空集的和为0是可能的）。

代码实现

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
    
        # 如果总和是奇数，直接返回 False
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True  # 空集的和为 0 是可能的
        
        # 遍历数组中的每个元素
        for num in nums:
            # 倒序遍历避免重复使用同一个元素
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]
        
        return dp[target]

复杂度分析

时间复杂度：$O(n * target)$，其中n是数组nums的长度，target是数组和的一半。

空间复杂度：$O(n)$。

32. Longest Valid Parentheses

原题链接

题目描述

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1 2	Input: s = "" Output: 0

Constraints:

0 <= s.length <= 3 * 10^4
s[i] is '(', or ')'.

解题方法

动态规划

使用动态规划（Dynamic Programming，DP）来求解最长有效括号子串问题也是一种常见的方法。动态规划的思路是通过构建一个 dp 数组来记录每个位置的有效括号子串的长度。

思路：

设dp[i]表示以i位置结尾的最长有效括号子串的长度。
状态转移方程：
- 如果s[i] == '('，则dp[i] = 0，因为以(结尾的子串不可能是有效的。
- 如果s[i] == ')'，我们需要考虑两种情况：
  - 如果s[i-1] == '('，说明我们找到一个有效的括号对()，此时dp[i] = dp[i-2] + 2（如果i-2有效括号子串存在的话）。
  - 如果s[i-1] == ')'，需要看s[i - dp[i-1] - 1] == '('，如果是(，则dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]，表示匹配到的括号对子串的长度加上前面有效括号子串的长度。

栈

这道题的目的是求一个只包含(和)的字符串中，最长有效括号子串的长度。

思路：

栈法：使用一个栈来帮助判断括号的匹配。栈中的元素保存的是括号的索引。
- 初始时，栈中放一个-1，用来表示一个基准值，方便计算有效子串的长度。
- 遍历字符串的每个字符：
  - 如果遇到(，将当前索引压入栈中。
  - 如果遇到)，则弹出栈顶元素，表示匹配到了一个(。
    - 如果栈为空，说明当前)没有匹配的(，将当前索引压入栈中作为新的基准值。
    - 如果栈不为空，则通过当前索引 - 栈顶元素来计算有效括号子串的长度。

代码实现

动态规划

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        
        dp = [0] * n  # 初始化dp数组
        max_length = 0  # 记录最长有效括号子串的长度

        for i in range(1, n):
            if s[i] == ')':
                # 如果前一个字符是 '('，即形成一对有效括号()
                if s[i - 1] == '(':
                    dp[i] = (dp[i - 2] if i - 2 >= 0 else 0) + 2
                # 如果前一个字符是 ')'，并且当前可以与之前的有效括号子串配对
                elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
                    dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] - 2 >= 0 else 0)
                
                max_length = max(max_length, dp[i])
        
        return max_length

栈

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]  # 栈初始化，包含一个基准值
        max_length = 0  # 记录最长有效括号子串的长度

        for i, char in enumerate(s):
            if char == '(':  # 遇到 '('，入栈
                stack.append(i)
            else:  # 遇到 ')'，出栈
                stack.pop()
                if not stack:  # 如果栈为空，说明当前的')'没有匹配的'('
                    stack.append(i)  # 将当前的索引作为新的基准值
                else:
                    # 计算当前有效括号子串的长度
                    max_length = max(max_length, i - stack[-1])

        return max_length

复杂度分析

方法	时间复杂度	空间复杂度
动态规划	$O(n)$	$O(n)$
栈	$O(n)$	$O(n)$