14-动态规划

背包问题

01背包(选或不选)

01背包

输入：n件物品，背包容量c，各物品容量weights、价值values，各物品数量都为1
输出：把背包尽量装满获得的最大价值。

暴力法(每个物品选或不选)

二维DP写法(标准)

DP 01背包

DP数组定义

dp[i][j]：从下标[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

递推公式

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]] + values[i])
- 放或不放物品i，取价值大者
$dp [i] [j] = max (\underset{不放物品 i}{\underset{⏟}{dp [i - 1] [j]}}, \underset{放物品 i}{\underset{⏟}{dp [i - 1] [j - w [i]] + v [i]}})$
不放物品i：最大价值为dp[i-1][j]
放物品i：dp[i-1][j-w[i]] + 放物品i后的新增价值
- 背包容量剩余 j-w[i]，
- 在物品[0,i-1]任取，放进容量为j-w[i]的最大价值：dp[i-1][j-w[i]]
- 放物品i的价值 v[i]

DP初始化

dp[0][0-n]：仅放物品0，背包容量由0到n的最大价值。0或者value[0]
其余均初始化为0

递推遍历顺序

物品：从1到n
容量：从0到capacity，从小到大。
先遍历物品，再遍历容量。反之也可以。

dp[1][4]推导示例

物品1 不放：dp[1][4]=dp[0][4]
物品1 放：dp[1][4] = dp[0][1] + values[1]
- 目前：背包容量=4，物品1容量=3，则剩余容量是4-3=1，
- 则：容量为1，从下标[0-0]的物品里取的最大价值，dp[0][1]
dp[1][4] = max(dp[0][4], dp[0][1] + 物品1的价值)

不放物品1

放物品1

python

def knapsack01_2d(self, weights: List[int], values: List[int], capacity: int) -> int:
    """01背包，标准dp二维数组写法，给定容量，尽量装满背包，能获得的最大价值"""

    if not weights or not values or capacity <= 0:
        return 0

    # n个物品
    n = len(weights)

    # dp[i][j]: 在[0-i]中任意选，容量为j，获得的最大价值
    dp = [[0]*(capacity+1) for _ in range(n)]

    # 初始化，仅放第0个物品的最大价值
    for j in range(capacity+1):
        # 背包容量足够放置物品0
        if j >= weights[0]:
            dp[0][j] = values[0]


    # 递推计算最大价值，先循环物品，再背包容量
    for i in range(1, n):
        # [0,i] 任选物品，计算在各容量下最大价值
        for j in range(capacity+1):
            # 背包容量足够放置物品i
            if weights[i] <= j:
                # 递推公式：max(不放物品i, 放物品i)的最大价值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i])
            else:
                # j太小，不能防止i，只能选择不放物品i
                dp[i][j] = dp[i-1][j]

    return dp[n-1][capacity]

一维DP写法(滚动数组,效率高)

一维DP滚动数组写法

dp定义

dp[j]：容量为j的背包，所背的最大价值。

dp迭代公式

dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
$dp [j] = max (\underset{不放物品 i}{\underset{⏟}{dp [j]}}, \underset{放物品 i}{\underset{⏟}{dp [j - w [i]] + v [i]}})$
dp[j]：自己相当于dp[i-1][j]
dp[j-weights[i]] + values[i]：容量为x的背包 + 放物品i的价值。

遍历顺序

物品：从0到n。
背包容量：必须从大到小遍历，防止重复放入物品。
- 若从小到大，则物品可多次存放，为完全背包。
- 如：

python

def knapsack01_1d(self, weights: List[int], values: List[int], capacity: int) -> int:
    """01背包，dp 1维滚动数组，写法"""
    if not weights or not values or capacity <= 0:
        return 0

    n = len(weights)

    # dp[j]：去掉i，容量为j的背包的背满的最大价值
    dp = [0] * (capacity+1)

    # 初始化

    # 先遍历物品
    for i in range(n):

        # 从大到小反向遍历背包容量，因为防止重复状态
        for j in range(capacity, -1, -1):
            if j >= weights[i]:
                # 递推公式
                dp[j] = max(dp[j], dp[j-weights[i]]+values[i])

    return dp[capacity]

递归写法

python

pass

01完全背包

小心

物品数量不受限制，可以多次装载。

二维DP完全背包

dp[i][j]定义

从物品[0-i]，每个物品可以取无限次，放进容量为j的背包，可获得的最大价值。

dp[0][x]初始化

对每个dp[0][x]，需循环存放，直到放满该容量。while x >= w[0]

dp[i][j]递推公式

完全不放物品i：dp[i][j] = dp[i-1][j]
再放1次物品i：dp[i][j]=dp[i][j-weights[i]]+values[i]。
- 背包容量为x，再放物品i的价值，再放时，物品列表是[0,i]，不是[0,i-1]
$dp [i] [j] = max (\underset{完全不放物品 i}{\underset{⏟}{dp [i - 1] [j]}}, \underset{再放 1 次物品 i}{\underset{⏟}{dp [i] [j - w [i]] + v [i]}})$
对比普通01背包
$dp [i] [j] = max (\underset{不放物品 i}{\underset{⏟}{dp [i - 1] [j]}}, \underset{放物品 i}{\underset{⏟}{dp [i - 1] [j - w [i]] + v [i]}})$

递推遍历顺序

物品：从1到i
背包容量：从小到大。
先背包、再物品也可以。

python

def complete_knapsack_2d(self, weights: List[int], values: List[int], capacity: int) -> int:
    """完全背包 二维dp写法"""

    if not weights or not values or capacity <= 0:
        return 0

    n = len(weights)

    # dp[i][j]: 从物品[0-i]中，不限物品数量，装到容量为j的背包中，获得的最大价值
    dp = [[0]*(capacity+1) for _ in range(n)]

    # 初始化仅物品0的价值dp[0][x]
    for j in range(capacity+1):
        c = j
        # 可以存放多次物品
        while c >= weights[0]:
            dp[0][j] += values[0]
            c -= weights[0]

    # 递推计算
    for i in range(1, n):
        # 计算物品[0-i]的各容量最大价值
        for j in range(capacity+1):
            if weights[i] <= j:
                # 放置物品i, 递推公式，放和不放选更大。注意dp[i][j-w[i]]，
                dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i]]+values[i])
            else:
                # 不放置物品i
                dp[i][j] = dp[i-1][j]
    # 最终结果
    return dp[n-1][capacity]

一维DP完全背包

一维DP滚动数组写法

dp定义

dp[j]：容量为j的背包，所背的最大价值。

dp迭代公式

dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
$dp [j] = max (\underset{不放物品 i}{\underset{⏟}{dp [j]}}, \underset{放物品 i}{\underset{⏟}{dp [j - w [i]] + v [i]}})$
dp[j]：自己，相当于dp[i-1][j]，上一轮的，但可以多次存放
dp[j-weights[i]] + values[i]：容量为x的背包 + 放物品i的价值。

遍历顺序

物品：从0到n。
背包容量：必须从小到大遍历，物品可重复存放。
- 若从大到小，则物品不可多次存放，为普通01背包。

python

def complete_knapsack_1d(self, weights: List[int], values: List[int], capacity: int) -> int:
    """完全背包，1维DP写法，从小到大遍历容量"""

    if not weights or not values or capacity <= 0:
        return 0

    n = len(weights)

    # dp[j]：容量为j，物品可重复放置，装满背包的最大价值
    dp = [0] * (capacity+1)

    # 递推遍历，先物品，再容量
    for i in range(n):
        # 递推计算物品为[0-i]时，背包各容量的价值

        # 物品必须从小到大遍历，每个物品可重复取
        for j in range(capacity+1): 
            if j >= weights[i]:  
                # 递推公式
                dp[j] = max(dp[j], dp[j-weights[i]]+values[i])  

    # 最终结果
    return dp[capacity]

题目

01-70-爬楼梯

leetcode-70

输入：n阶楼梯。一次可爬1个或2个楼梯。
输出：最多多少种方法到达楼顶。

DP爬楼梯方法数

dp[i]：到达第i个楼梯的方法数。
dp[i] = dp[i-1] + dp[i-2]，从i-1爬1到达或 从i-2爬2到达。

python

def climbStairs(self, n: int) -> int:
    """爬楼梯，爬1个或2个，有多少种方法到达n"""

    # 特殊情况
    if n <= 2:
        return n

    # dp[i] 爬到第i阶的方法数
    dp = [0] * (n+1)  

    # 1种，只能走1步
    dp[1] = 1
    # 2种，走2个1步，或1次走2步
    dp[2] = 2

    for i in range(3, n+1):
        # 递推
        dp[i] = dp[i-1] + dp[i-2]  

    return dp[n]

02-118-杨辉三角

leetcode-118

输入：numRows
输出：杨辉三角的前numRows行。
杨辉三角：每个数=左上方数+右上方数

DP三角求和

提示

第i行：共i+1个元素
初始化首尾值为1：j=0, j=i：dp[i][j]=0
递推计算中间值：dp[i][j] = dp[i-1][j-1]+dp[i-1][j]

python

def generate(self, numRows: int) -> List[List[int]]:
    """杨辉三角，dp递推"""
    res = []

    for i in range(numRows):
        # 第i行，共i+1个元素，
        row = [0] * (i+1)
        res.append(row)

        # 初始首尾值
        res[i][0] = 1
        res[i][i] = 1

        # 递推计算中间值
        for j in range(1, i):
            res[i][j] = res[i-1][j-1] + res[i-1][j]
    return res

03-198-打家劫舍

leetcode-198

输入：每个房屋的金额数组
目标：偷每个房间的钱，相邻两个房间 不能同时偷，会报警。
输出：能偷的最高金额和

偷房间钱最高金额

重要

初始值：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
dp[i]：第i个房间完成时的最大收益，偷或不偷 取其大
- 偷：dp[i] = dp[i-2] + nums[i]
- 不偷：dp[i] = dp[i-1]

04-279-完全平方数

leetcode-279

输入：n
输出：和为n的完全平方数的最少数量。
完全平方数：1、4、9
示例：12 = 4+4+4 --> 3；13 = 4 + 9 --> 2

完全平方数求和最少数量

DP完全平方数求和

dp数组：从0到n，n+1个位置，求最少数量。初始化：dp[0]=0，其余为正无穷，
dp[i]：凑出整数i 所需完全平方数的最少数量。
最后加入平方数为 $j$ ，平方和为 $j^{2}$ ，前面和 $i - j^{2}$ ，前面最少数量 $d p [i - j^{2}]$
j取值范围： $1 \leq j^{2} \leq i$
从1遍历 所有可能j，递推计算各自最少数量，取最小值为dp[i]

d p [i] = min (d p [i], d p [i - j^{2}] + 1), 1 \leq j^{2} \leq i

python

def numSquares(self, n: int) -> int:
    """完全平方和最少数量"""        
    # 从0到n，n+1个位置，求最少数量，初始化为正无穷
    dp = [float('inf')] * (n+1)

    # 初始化：凑出0的方法数是0
    dp[0] = 0

    # 依次遍历每个数，计算dp
    for i in range(1, n+1):
        j = 1
        # 尝试减去小于i的每个完全平方数和j*j，去算数量
        while j*j <= i:
            # 状态转移方程，最后一个增加的是j*j
            dp[i] = min(dp[i], dp[i-j*j] + 1)
            j += 1
    return dp[n]

05-322-零钱兑换

leetcode-322

输入：硬币数组coins，总金额amount
输出：凑成总金额的最少硬币数量，每种硬币数量无限；如果不能凑成总金额，返回-1
示例：[1,2,5], 11 --> 11=5+5+1 --> 3

硬币求和最少硬币数量

dp[i]：凑成金额i的最少硬币数量，初始化：dp[0]=0，其余为max_val
依次遍历求解 各金额的最少硬币数量
- 为凑成金额i，最后加入硬币为coin，前面为i-coin，
- 依次遍历所有可能coin，取最小可能性
$d p [i] = min (d p [i], d p [i - j] + 1), j \in coins, i - j \geq 0$

python

def coinChange(self, coins: List[int], amount: int) -> int:
    """求解硬币凑成总金额的所需最少硬币数量，dp"""

    # dp[i]：凑成金额i，所需的最少硬币数量，初始化为最大值，可为float(inf)或一个最大值
    max_val = amount + 1
    dp = [max_val] * (amount+1)
    # 金额0，所需硬币为0
    dp[0] = 0

    # 依次求解所有金额的最少硬币数量
    for i in range(1, amount+1):
        # 凑成金额i，最后加入硬币为coin，依次求解数量，取最小可能性
        for coin in coins:
            if i - coin >= 0:
                # 递推：dp[i] = dp[i-coin]+1，取最小值
                dp[i] = min(dp[i], dp[i-coin]+1)

    # 如果非最大值，则说明能凑；否则为不能凑
    return dp[amount] if dp[amount] != max_val else -1

06-139-单词拆分

leetcode-139

输入：字符串raw，字符串列表word_dict
输出：能否用字符串列表里的子串，去组成字符串s，子串可使用多次。

子串组成字符串可能性

dp[s]：能否组成字符串s，其中空字符串为True，方便后续prefix为空的情况。
raw中，从左至右，依次计算能否组成s，每次增加1个字符
- s = raw[0:i+1]，dp[s] = False
- s = prefix + word，遍历所有最后加入word，寻找能否组成s
  - 递推：若dp[prefix]为True，则dp[s]=True
- 最后加入子串为sub，前面为raw-sub

python

def wordBreak(self, raw: str, wordDict: List[str]) -> bool:
    """判断能否使用word_dict子串组成字符串raw"""

    # dp[s]：表示能否组成字符串s，空字符为True，方便后续prefix为True
    dp = {"": True}

    # raw从左到右，依次计算是否能组成字符串s
    for i in range(len(raw)):
        # 当前需要计算的字符串s
        s = raw[0:i+1]
        # 默认为False
        dp[s] = False

        # s中，最后一个加入的是word，即s=prefix+word，依次判断能否组成
        for word in wordDict:
            if not s.endswith(word):
                continue
            prefix = s[0:(len(s)-len(word))]
            # 找到一个可行的word，则说明能组成s，直接break
            if dp.get(prefix, False) is True:
                dp[s] = True
                break
    return dp[raw]

07-300-最长递增子序列

leetcode-300

输入：nums
输出：最长递增子序列的长度
示例：[10,9,2,5,3,7,101,18] --> 2,3,7,101 --> 4

最长递增子序列长度

dp[i]：以nums[i]结尾的最长递增子序列长度。初始化：dp[i]=1
j：i追加到前面序列末尾，前面序列以j结尾，遍历寻找最佳j
j取值范围：0<= j < i-1，nums[j] <= nums[i]
$d p [i] = max (d p [i], d p [j] + 1), j \in [0, i - 1], nums [i] \geq nums [j]$
结果：取max(dp)，最长序列，不一定结尾在末尾
时间： $O (n^{2})$

python

def lengthOfLIS(self, nums: List[int]) -> int:
    """最长递增公共子序列，dp"""
    n = len(nums)
    # dp[i]：数组0-i内的最长公共子序列长度
    dp = [1] * n

    # 依次遍历，求解各位置值
    for i in range(n):
        # 数字i，可追加到前面各子串后面，递推寻找最佳位置
        for j in range(i):
            if nums[j] < nums[i]:
                # 递推公式：dp[i]=dp[j]+1，取最大值
                dp[i] = max(dp[i], dp[j]+1)
    # 需要返回dp里的最大值，最大值不一定出现在末尾数字结尾
    return max(dp)

分堆贪心二分结尾数字最小值

分堆：每个堆存放1个最小元素，堆列表 从小到大递增。
tails[i]：长度为i+1的递增子序列中，结尾数字的最小值。
遍历数组，新元素进来
- 二分查找：在现有堆列表中寻找第一个大于val的堆。
  - 如果找到：新元素更小，用小值 贪心覆盖该堆堆顶大值。
  - 如果没找到：新元素更大，建立新堆，保证堆列表严格递增。
最终：堆列表长度i+1，为最短公共子序列长度，即找到长i+1列表结尾数字的最小值。
注意：堆顶元素列表并非实际公共子序列。

python

def lengthOfLIS_heap(self, nums: List[int]) -> int:
    """最长递增公共子序列，堆思想"""

    # tails[i]：长度为i+1的递增子序列中，结尾数字的最小值。分堆
    tails = []

    # 遍历元素，依次建堆覆盖
    for val in nums:    
        # 新元素进来

        # 在目前堆中，寻找该放入的位置，寻找第1个
        idx = self.binary_search(tails, val)
        if idx <= len(tails) - 1:
            # val比idx堆值更小，直接覆盖
            tails[idx] = val 
        else:
            # val比现有堆列表中所有值都更大，新建一个堆
            tails.append(val)
    # 返回堆列表长度x即可，即长度为x的递增子序列，结尾最小的元素为tails[x-1]
    return len(tails)

二分查找待插入位置

python

def binary_search(self, nums, target) -> int:
    """在递增数组中，寻找插入位置"""

    l, r = 0, len(nums)-1
    while l <= r:
        mid = l + (r-l) // 2
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            r = mid - 1
        else:
            l = mid + 1
    # 此时l>r，找不到目标值，l就是需要插入的位置
    return l

08-152-乘积最大子数组

leetcode-152

输入：nums
输出：最大连续子数组 乘积

正负数最大最小DP求最大乘积和

重要

max_dp[i]：以数字i结尾的最大子数组乘积。
min_dp[i]：以数字i结尾的最小子数组乘积。
根据正负 计算最大乘积和 max_dp[i]
- 当前为正数：期望前面越大越好，选max_dp[i-1] * nums[i]
- 当前为负数：期望前面越小越好，选min_dp[i-1] * nums[i]
根据正负 计算最小乘积和 min_dp[i]
- 正数：前面越小越好
- 负数：前面越大越好

python

def maxProduct(self, nums: List[int]) -> int:
    """正负数，最大连续子数组乘积，最大最小dp，根据正负来计算"""
    n = len(nums)
    # 乘积有正负，容易负负得正，因此需要2个dp来
    # max_dp[i]：以i结尾，最大连续子数组乘积
    max_dp = [0] * n
    # min_dp[i]：以i结尾，最小连续子数组乘积
    min_dp = [0] * n

    # 初始化
    min_dp[0] = nums[0]
    max_dp[0] = nums[0]

    # 遍历数字，递推
    for i in range(1, n):
        val = nums[i]

        if val > 0:
            # 正数，前面最大*nums[i]
            max_dp[i] = max(max_dp[i-1]*nums[i], nums[i])
            min_dp[i] = min(min_dp[i-1]*nums[i], nums[i])
        elif val < 0:
            # 负数，max和min，要反过来 前面最小*nums[i]
            max_dp[i] = max(min_dp[i-1]*nums[i], nums[i])
            min_dp[i] = min(max_dp[i-1]*nums[i], nums[i])
        else:
            # 0
            min_dp[i] = max_dp[i] = 0
    # 取最大
    return max(max_dp)

DP空间优化常数变量递推

直接记录当前位置的最大乘积、最小乘积，全局最大乘积res
直接遍历元素，递推计算最大乘积、最小乘积，最核心见代码

python

def maxProduct_dp_optimize(self, nums: List[int]) -> int:
    """正负数最大连续子数组乘积，最大最小dp，根据正负来计算，优化存储空间"""
    # 当前位置的最大乘积、最小乘积，和全局最终结果
    cur_max = nums[0]
    cur_min = nums[0]
    res = cur_max

    # 遍历递推
    for i in range(1, len(nums)):
        # 当前位置i结尾
        val = nums[i]
        temp_max = cur_max
        # 计算当前i位置结尾的最大最小连续子数组和，递推
        cur_max = max(nums[i], max(val*cur_max, val*cur_min))  
        cur_min = min(nums[i], min(val*temp_max, val*cur_min))  
        # 更新最大乘积
        res = max(res, cur_max)
    return res

错误写法

忽略了正负数问题

python

def maxProduct_bad(self, nums: List[int]) -> int:
    """最大连续子数组乘积，dp"""

    # dp[i], 以数字i结尾，最大连续子数组乘积和
    dp = [0] * len(nums)
    # 初始化0
    dp[0] = nums[0]

    # 遍历元素，依次求解
    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1]*nums[i], nums[i])  

    # 返回最大值
    return max(dp)

09-416-分割等和子集

leetcode-416

输入：正数组nums
输出：能否把分成两个等和的子数组。

分割等和子集

数组求和，和为偶数，才能均分；记一半为target

DP 数组和均分

DP数组和均分

01背包问题转换

物品：nums
背包容量：target
物品重量：每个数的值。
物品价值：每个数的值。背包最大价值：各数求和
答案判断：容量为target的背包正好装满，最大价值为target

python

def canPartition_dp1d(self, nums: List[int]) -> bool:
    """数组和均分，使用01背包，dp1d写法"""
    if not nums or len(nums) <= 1:
        return False
    # 总和为奇数，直接返回False
    sum_value = sum(nums)
    if sum_value % 2 != 0:
        return False
    # 目标价值，期望为一半
    target = sum_value // 2

    # 01背包问题：物品nums, 背包容量target, 物品价值 数值，物品重量 数值
    # 期望：target的背包最大价值为target，刚好装满
    # dp[j]：容量为j时背包，背满的最大价值，装下最大的数字和
    dp = [0] * (target+1)  

    # 递推计算数字[0-i]，各容量背包的最大价值
    for i in range(len(nums)):
        num = nums[i]
        # 01背包，容量从大到小计算，放置重复
        for j in range(target, -1, -1):
            if num <= j:
                # 可选num，max 选i或不选i
                dp[j] = max(dp[j], dp[j-num]+num)
            else:
                # 不选num
                pass
    # 容量target背包恰好装满等于target
    return dp[target] == target

10-32-最长有效括号

leetcode-32

输入：只包含( ) 左右括号的字符串。
输出：最长有效括号 长度。
有效括号：()()、(())，每个左括号都有对应的右括号做匹配。
无效括号：(()

DP 最长有效括号(递推条件判断)

DP 最长有效括号

定义及初始化

dp[i]：0-i子串，最长有效括号
初始化：dp[0]=0, dp[1]=2：有效括号(), dp[1]=0 ： 其他情况

递推公式

s[i]==(：无法构成有效括号，dp[i]=0
s[i]==)：
- s[i-1]==(：前面括号 + ()。dp[i]=dp[i-2] + 2。
- s[i-1]==)：前面括号 + )) --> (或) + (xx有效括号?) + )
  - 两个概念
    - dp[i-1]：以i-1结尾的最长有效括号长度
    - sym_pos = i-dp[i-1]-1：跳过中间有效括号，左边的第一个字符
  - s[sym_pos] == (：左边之前的括号字符串 + ( + 中间括号字符串 + 当前右括号)
    - dp[i] = dp[i-1] + 2 + dp[sym_pos-1]
  - s[sym_pos] == )：dp[i] = 0

python

def longestValidParentheses_dp_simple(self, s: str) -> int:
    """最长有效括号，dp写法，简洁版，核心是递推边界条件"""

    if not s or len(s) <= 1:
        return 0

    n = len(s)

    # dp[i]: 以i结尾子串，最长有效括号长度
    dp = [0] * n

    # 初始化dp[0] dp[1]
    dp[0] = 0
    if s[0:2] == '()':
        dp[1] = 2

    # 递推计算剩余i结尾的最长有效长度
    for i in range(2, n):      
        # 最右侧为左括号，不成有效括号
        if s[i] == '(':
            continue    
        # 判断i-1为(、)的情况   
        if s[i-1] == '(':
            # 直接和前面配对
            dp[i] = dp[i-2] + 2
        elif s[i-1] == ')':
            # 左侧括号字符串 + 左侧对称括号 + 中间括号字符串 + 当前右括号
            # dp[i-1] 中间括号字符串长度
            if dp[i-1] == 0:
                # 中间不成括号，自然dp[i]也不成括号，为0
                continue
            # 左侧对称括号位置
            sym_pos = i - dp[i-1] - 1
            if sym_pos == 0:
                # sym_pos 左边没有了，左侧必须是(
                if s[sym_pos] == '(':
                    dp[i] = dp[i-1] + 2
            elif sym_pos >= 1:
                # sym_pos 左侧仍然有字符串，左侧必须是(
                if s[sym_pos] == '(':
                    dp[i] = dp[sym_pos-1] + dp[i-1] + 2
    # 取最大值，不一定非得以s[n-1]结尾
    return max(dp)

python

def longestValidParentheses_dp_full(self, s: str) -> int:
    """最长有效括号，dp写法，注意递推公式，判断条件"""

    if not s or len(s) <= 1:
        return 0

    n = len(s)

    # dp[i]：以i结尾的子串，最长有效括号长度
    dp = [0] * n

    # 初始化 dp[0]和dp[1]
    dp[0] = 0
    if s[0] == '(' and s[1] == ')':
        dp[1] = 2

    # 递推计算其余以i结尾的子串，最长有效括号长度
    for i in range(2, n):
        if s[i] == '(':
            # 以左括号结尾，属于无效括号
            dp[i] = 0
        elif s[i] == ')':
            # 以右括号结尾，可能属于有效括号
            if s[i-1] == '(':
                # 前面括号 + ()
                dp[i] = dp[i-2] + 2
            elif s[i-1] == ')':
                # 左侧括号字符串 + 左侧对称括号 + 中间括号串 + )
                if dp[i-1] == 0:
                    # 中间不成有效括号, dp[i]也不成有效括号
                    dp[i] = 0
                else:
                    # 找到和i对称的字符位置
                    sym_pos = i-dp[i-1]-1
                    if sym_pos < 0:
                        # 无对称位置，不成对
                        dp[i] = 0
                    elif sym_pos == 0:
                        # 有成对位置
                        if s[sym_pos] == '(':
                            dp[i] = 2 + dp[i-1]
                        else:
                            dp[i] = 0
                    else:
                        # 核心，递推公式，左侧有效括号 + 中间有效括号 + 对称()括号长度2
                        if s[sym_pos] == '(':
                            dp[i] = dp[sym_pos-1] + dp[i-1] + 2
                        else:
                            dp[i] = 0
    # 最长长度，从dp里选最大值，不一定非得以s[n-1]结尾
    return max(dp)

栈最长有效括号(迭代更新最大长度)

信息

栈，初始化 -1下标入栈，-1作起点，作计算长度。i-last_idx，不用+1
遍历字符s[i]
- s[i] = 左括号：下标i入栈
- s[i] = 右括号：栈顶出栈
  - 栈为空：右括号多了，因为栈底本有-1，记录新的起点，i入栈
  - 栈不为空：计算长度：i-stack[-1]

python

def longestValidParentheses_stack(self, s: str) -> int:
    """最长有效括号，栈写法"""
    if not s or len(s) <= 1:
        return 0

    # 栈，记录下标，-1入栈，用于计算长度
    stack = []
    stack.append(-1)

    # 有效括号最大长度
    maxlen = 0

    # 遍历ch
    for i, ch in enumerate(s):
        if ch == '(':
            # 左括号入栈
            stack.append(i)
        elif ch == ')':
            # 右括号栈顶出栈，判断合理、更新长度
            stack.pop()

            if not stack:
                # 栈为空，说明左括号不够，当前不匹配，当前i入栈，记录新的起点
                stack.append(i)
            else:
                # 栈有值，更新最大有效括号长度
                last_idx = stack[-1]  
                curlen = i - last_idx  
                maxlen = max(maxlen, curlen)  
    return maxlen

背包问题 ​

01背包(选或不选) ​

暴力法(每个物品选或不选) ​

二维DP写法(标准) ​

一维DP写法(滚动数组,效率高) ​

递归写法 ​

01完全背包 ​

二维DP完全背包 ​

一维DP完全背包 ​

题目 ​

01-70-爬楼梯 ​

DP爬楼梯方法数 ​

02-118-杨辉三角 ​

DP三角求和 ​

03-198-打家劫舍 ​

偷房间钱最高金额 ​

04-279-完全平方数 ​

完全平方数求和最少数量 ​

05-322-零钱兑换 ​

硬币求和最少硬币数量 ​

06-139-单词拆分 ​

子串组成字符串可能性 ​

07-300-最长递增子序列 ​

最长递增子序列长度 ​

分堆贪心二分结尾数字最小值 ​

08-152-乘积最大子数组 ​

正负数最大最小DP求最大乘积和 ​

DP空间优化常数变量递推 ​

错误写法 ​

09-416-分割等和子集 ​

DP 数组和均分 ​

10-32-最长有效括号 ​

DP 最长有效括号(递推条件判断) ​

栈最长有效括号(迭代更新最大长度) ​

背包问题

01背包(选或不选)

暴力法(每个物品选或不选)

二维DP写法(标准)

一维DP写法(滚动数组,效率高)

递归写法

01完全背包

二维DP完全背包

一维DP完全背包

题目

01-70-爬楼梯

DP爬楼梯方法数

02-118-杨辉三角

DP三角求和

03-198-打家劫舍

偷房间钱最高金额

04-279-完全平方数

完全平方数求和最少数量

05-322-零钱兑换

硬币求和最少硬币数量

06-139-单词拆分

子串组成字符串可能性

07-300-最长递增子序列

最长递增子序列长度

分堆贪心二分结尾数字最小值

08-152-乘积最大子数组

正负数最大最小DP求最大乘积和

DP空间优化常数变量递推

错误写法

09-416-分割等和子集

DP 数组和均分

10-32-最长有效括号

DP 最长有效括号(递推条件判断)

栈最长有效括号(迭代更新最大长度)