一维 DP
动态规划的核心在于把一个全局最优问题拆解为结构稳定、可复用的子问题。
第一，状态定义（State）。 必须明确：一个状态精确表示“问题在某个阶段下，已知的信息是什么”。状态要最小且完备，既不能缺信息导致无法转移，也不能冗余导致维度爆炸。经验上，状态往往回答“在前 i 个元素 / 到第 i 步 / 以某个条件结尾时，最优解是多少”。
第二，状态转移（Transition）。 这是动态规划的本质。需要找到状态之间的递推关系，通常来源于“最后一步如何来”。形式上表现为 dp[i] = min / max / sum (由若干个更小状态推导)。 一个关键检验标准是：转移只依赖于更小规模的子问题，不存在环依赖。
第三，初始条件（Base Case）。 必须给出最小规模问题的确定解，例如 dp[0]、dp[1]。 初始条件不是“为了代码不报错”，而是数学意义上的边界，否则整个递推将失去锚点。
第四，计算顺序（Order）。 要保证在计算 dp[i] 时，其依赖的状态已经被计算过。这决定了是自底向上（迭代）还是自顶向下（记忆化搜索）。本质上，这是对状态依赖关系的拓扑顺序安排。
第五，结果定义与优化（Answer & Optimization）。 需要明确：最终答案是某一个状态，还是所有状态中的最优值。同时判断是否可以进行空间优化（如只依赖前一两个状态，滚动数组降维）。
一句话总结： 动态规划 = 合理的状态表达 + 无环的状态转移 + 正确的边界 + 合法的计算顺序。 只要这四点成立，代码只是自然推导的结果。
对于动态规划问题，可以拆解为如下五步曲，
1.确定dp数组（dp table）以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？ 因为一些情况是递推公式决定了dp数组要如何初始化！
70. 爬楼梯¶
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
核心思路：
到第 i 阶的方法数 = 到第 i-1 阶的方法数 + 到第 i-2 阶的方法数
class Solution:
def climbStairs(self, n: int) -> int:
# 初始化 dp[0] 和 dp[1]
dpi_2, dpi_1 = 1, 1 # dp[0]=1, dp[1]=1
for _ in range(n - 1):
# 状态转移方程
dpi = dpi_1 + dpi_2
# 滚动更新 dp[i-2] 和 dp[i-1] 的值
dpi_2, dpi_1 = dpi_1, dpi
return dpi_1
n = 1
print(Solution().climbStairs(n))
1
时间复杂度为 O(n)。函数中仅包含一次长度为 n−1 的 for 循环，每次循环只进行常数次加法与变量赋值操作，不存在嵌套循环或递归，因此整体时间随 n 线性增长。
空间复杂度为 O(1)。算法没有使用长度为 n 的 dp 数组，而是仅用三个标量变量 dpi_2、dpi_1、dpi 来滚动保存状态，所占额外空间与输入规模 n 无关，因此为常数空间复杂度。需要注意的是，这里讨论的是额外空间复杂度，不包含输入参数 n 本身。
本质上，该实现利用了状态转移方程 dp[i] = dp[i−1] + dp[i−2]， 并通过“只保留最近两个状态”完成了对标准 DP 解法的空间压缩。
118. 杨辉三角¶
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
核心思路：
第 i 行（i 从 1 开始）长度就是 i。
两端固定为 1。
中间列 j（2 ≤ j ≤ i-1）由上一行相邻两数相加得到： 第 i 行第 j 列 = 第 (i-1) 行的第 (j-1) 列 + 第 (i-1) 行的第 j 列。
from typing import List
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [] # 存储所有行的结果
for i in range(1, numRows + 1): # 逐行生成，第 i 行有 i 个元素
cur_row = [1] * i # 初始化当前行，首尾均为 1
# 更新中间元素（首尾固定为 1，无需处理）
# 当前行第 j 个元素 = 上一行第 j-1 与第 j 个元素之和
for j in range(1, i - 1):
cur_row[j] = ans[i-2][j-1] + ans[i-2][j]
ans.append(cur_row) # 将当前行加入结果
return ans
numRows = 5
print(Solution().generate(numRows))
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
时间复杂度方面： 外层循环从 i = 1 到 numRows，一共执行 numRows 次。 第 i 行内部有一个长度为 i 的数组初始化（[1] * i），这是 O(i)。 随后内层循环 j 从 1 到 i−2，执行约 i−2 次，每一步是常数时间的加法。 因此第 i 行的总体时间是 O(i)。 将所有行累加，总时间复杂度为 O(1 + 2 + 3 + … + numRows) = O(numRows²)。
空间复杂度方面： 输出结果 output 本身需要存储杨辉三角的全部元素，总元素个数为 1 + 2 + … + numRows = O(numRows²)。 除输出外，只使用了常数级的临时变量（cur 指向当前行，不额外叠加存储）。 因此额外空间复杂度（不计输出）为 O(1)， 总空间复杂度（计入输出）为 O(numRows²)。
198. 打家劫舍¶
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
到第 i 间房时只有两种选择：不偷（保持前一家的最优），或偷（当前金额 + 前两家的最优）。 取两者最大即可，像斐波那契那样滚动更新。
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
"""
dp[i] 表示考虑到第 i 间房（下标 i），能偷到的最高金额。
转移：要么不偷 i（保持 dp[i-1]），要么偷 i（nums[i] + dp[i-2]）
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
只需两个变量滚动保存 dp[i-2], dp[i-1]，空间 O(1)。
"""
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
# 初始化 dp[0] 和 dp[1]
dp_i_2 = nums[0]
dp_i_1 = max(nums[0], nums[1])
# 从第 2 间（下标 2）开始迭代
for i in range(2, n):
# 状态转移方程
dp_i = max(dp_i_1, dp_i_2 + nums[i])
# 滚动更新 dp[i-2] 和 dp[i-1] 的值
dp_i_2, dp_i_1 = dp_i_1, dp_i
return dp_i_1
nums = [1,2,3,1]
print(Solution().rob(nums))
4
时间复杂度： 代码只对数组 nums 做了一次线性遍历。初始化是常数时间，for i in range(2, n) 循环执行 n−2 次，每一步只包含常数次比较与加法运算。因此整体时间复杂度为 O(n)。
空间复杂度： 算法未使用与 n 成比例的额外数据结构，仅使用了 dp_i_2、dp_i_1、cur 等常数个变量来滚动保存状态。因此 额外空间复杂度为 O(1)。 需要注意的是，输入数组 nums 不计入额外空间。
279. 完全平方数¶
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
核心思路（DP，完全背包视角）
定义：dp[i] 表示凑成和为 i 的最少完全平方数个数。
转移（最后一步法）：枚举所有平方数 s ∈ {1,4,9,..., s≤i}， dp[i] = min(dp[i], dp[i - s] + 1) 含义：最后一次放入平方数 s，前面已把 i-s 最优凑好。
初始化：dp[0]=0；其余设大数（如 n+1）。从 i=1..n 递推即可。
class Solution:
def numSquares(self, n: int) -> int:
# 1. 预处理：构造所有 <= n 的完全平方数
square_list = []
k = 1
while k * k <= n:
square_list.append(k * k) # 收集平方数：1, 4, 9, 16, ...
k += 1
# 2. 定义 dp 数组
# dp[i] 表示：组成整数 i 所需的最少完全平方数个数
# 初始化为 n，是因为最坏情况：全部用 1 组成（最多 n 个 1），且构造好边界
dp = [n] * (n + 1)
dp[0] = 0
# 3. 完全背包动态规划
for i in range(1, n + 1): # 遍历“背包容量”i
for s in square_list: # 遍历“物品”（平方数）
if s > i:
break # 如果当前平方数大于 i，后面更大，直接停止
# 状态转移方程；若最后一个使用的是平方数 s，那么问题就转化为：组成 i-s 需要的最少个数 + 当前这个 s
dp[i] = min(dp[i], dp[i - s] + 1)
return dp[-1]
n = 13
print(Solution().numSquares(n))
2
复杂度分析 设 n 为输入值，不超过 n 的平方数个数为 ⌊√n⌋。外层循环遍历 i=1…n，内层循环遍历所有平方数，因此时间复杂度为 O(n√n)。 使用了长度为 n+1 的 dp 数组，以及一个大小为 √n 的平方数列表，主导空间开销来自 dp 数组，因此空间复杂度为 O(n)。
322. 零钱兑换¶
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
核心思路：
与完全平方数思路相同，注意最后对dp[-1]的检查，以及不需要每个时刻检查是否能完成零钱兑换，完成不了，他的最小组合是amount+1,后续也不会使用到该状态
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# dp[i] 表示：凑成金额 i 所需的最少硬币数
# 初始化为 amount+1（不可能达到的最大值，相当于正无穷）
dp = [amount+1] * (amount+1)
dp[0] = 0 # 金额为 0 时，不需要硬币
coins.sort() # 排序，便于后面提前 break，否则提前break会导致出错
# 遍历每个金额 i（背包容量）
for i in range(1, amount+1):
# 遍历每个硬币（物品）
for s in coins:
if s > i:
break # 硬币面值大于当前金额，停止
# 状态转移：
# 若最后使用的是硬币 s，
# 那么 dp[i] = dp[i-s] + 1
dp[i] = min(dp[i], dp[i-s] + 1)
# 若最终仍是初始值，说明无法凑成
return dp[-1] if dp[-1] < (amount+1) else -1
coins = [1, 2, 5]
amount = 11
print(Solution().coinChange(coins, amount))
3
这是一个完全背包的一维动态规划解法，
时间复杂度方面。 外层循环遍历金额 i 从 1 到 amount，共 amount 次；内层循环遍历硬币面值 coins，最坏情况下每个 i 都需要遍历全部硬币数量 m。排序带来的 O(m log m) 只执行一次，且通常远小于 DP 主循环。因此总体时间复杂度为 O(amount × m)，排序为次要开销。
空间复杂度方面。 使用了一个长度为 amount+1 的一维 dp 数组，dp[i] 表示凑成金额 i 所需的最少硬币数；除 dp 外只使用常数级变量。因此空间复杂度为 O(amount)。
补充说明。
排序 coins 的作用是利用 j > i 提前 break，在平均情况下可以减少内层循环次数，但不改变最坏情况下的渐进复杂度。
139. 单词拆分¶
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
核心思路：
定义状态：dp[i] 表示前缀 s[:i] 能否由字典单词拼出。
初始：dp[0] = True（空串可被“空选择”拼出）。
转移：枚举切分点 j < i，若 dp[j] == True 且 s[j:i] 在字典中，则 dp[i] = True。 枚举“最后一个单词是谁”， 将大问题拆解为更小的前缀子问题。
答案：返回 dp[-1]。
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
# dp[i] 表示：前 i 个字符是否可以被拆分
dp = [False] * (n + 1)
dp[0] = True # 空字符串一定可以被拆分
for i in range(1, n + 1):
for word in wordDict:
j = len(word)
# 必须保证 i >= j，避免负索引
if i >= j and s[i - j:i] == word:
dp[i] = dp[i] or dp[i - j]
return dp[n]
s = "leetcode"
wordDict = ["leet", "code"]
print(Solution().wordBreak(s, wordDict))
True
1.时间复杂度
n = 字符串长度; m = 字典中单词数量; k = 单词平均长度
外层循环：n 次; 内层遍历单词：m 次; 每次字符串比较：O(k)
因此总时间复杂度：O(n × m × k)
2.空间复杂度
dp 数组长度为 n+1
空间复杂度： O(n)
300. 最长递增子序列¶
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
核心思路：
状态：dp[i] 表示“以 nums[i] 结尾”的 LIS 长度。
转移：看所有 j<i 且 nums[j]<nums[i]，取 max(dp[j])+1。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
# 初始化 dp 数组，dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
dp = [1] * n
for i in range(1, n):
for j in range(i):
# 状态转移方程，max一定要存在，为了遍历对比
if nums[j] < nums[i]:
dp[i] = max(dp[j] + 1, dp[i])
return max(dp)
nums = [10,9,2,5,3,7,101,18]
print(Solution().lengthOfLIS(nums))
4
时间复杂度： 外层循环 i 从 1 到 n−1，共 n 次； 内层循环 j 从 0 到 i−1，平均约 n/2 次，最坏为 n 次。 每一步只做常数级比较与赋值。
因此总体时间复杂度为： O(n²)
空间复杂度： 使用了一个长度为 n 的 dp 数组，除输入外没有额外结构。 空间复杂度为：O(n)
最长递增子序列（LIS）的核心思想可以从两个层次理解：首先是动态规划的直观定义，其次是在此基础上通过贪心与二分查找进行优化。
从问题本质来看，LIS要求在保持原有顺序的前提下，找到一个长度最大的严格递增子序列。最直接的思路是动态规划：定义 dp[i] 表示以 nums[i] 作为结尾的最长递增子序列长度。为了计算 dp[i]，需要查看所有 j < i 的位置，如果 nums[j] < nums[i]，则可以把 nums[i] 接在 nums[j] 之后，因此有状态转移 dp[i] = max(dp[i], dp[j] + 1)。这种方法需要两层循环，时间复杂度为 O(n²)。
进一步观察这个过程会发现，动态规划实际上在做一件事情：对于不同长度的递增序列，我们只关心“这个长度的递增序列最小的结尾是多少”。原因是结尾越小，将来就越容易接上更大的元素，从而形成更长的递增序列。因此可以维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列能够达到的最小结尾。这个数组具有单调递增的性质。
遍历数组中的每一个元素 num 时，如果 num 比 tails 的最后一个元素大，就说明可以扩展当前最长序列，直接将 num 加入 tails；否则，就在 tails 中找到第一个大于等于 num 的位置，并用 num 替换该位置的元素。这样做的意义在于：保持相同长度的递增序列时，让结尾尽可能小，从而为后续元素留下更大的增长空间。由于 tails 始终是有序的，因此寻找替换位置可以使用二分查找，将查找复杂度从线性降低到对数。
随着遍历的进行，tails 数组会逐渐维护出不同长度递增序列的最优结尾状态。虽然 tails 本身不一定对应真实存在的一条完整递增子序列，但它的长度始终等于当前能够构成的最长递增子序列长度。因此最终 tails 的长度就是 LIS 的长度。该方法在每个元素上执行一次二分查找，总时间复杂度为 O(n log n)，空间复杂度为 O(n)。
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# tails[i] 表示：
# 长度为 i+1 的递增子序列中，所有可能情况里“最小的结尾元素”
# 维护这个数组的目的：让结尾尽可能小，从而更容易接上后面的数字
# 注意：tails 本身不一定是真实的 LIS，只是用于维护最优状态
tails = []
# 依次遍历数组中的每个数字
for num in nums:
# --- 使用二分查找 num 在 tails 中应该插入的位置 ---
# 我们要找到 tails 中第一个 >= num 的位置
# 因为 tails 是单调递增的，所以可以二分查找
left, right = 0, len(tails)
while left < right:
mid = (left + right) // 2
# 如果 tails[mid] < num
# 说明 num 应该在右侧
if tails[mid] < num:
left = mid + 1
else:
# 否则 num 应该在 mid 或更左的位置
right = mid
# 循环结束后
# left 就是第一个 >= num 的位置
# --- 更新 tails ---
# 如果 num 比 tails 中所有元素都大
# 说明可以扩展一个更长的递增序列
if left == len(tails):
tails.append(num)
else:
# 否则，用 num 替换 tails[left]
# 表示：同样长度的递增序列，我们找到了一个更小的结尾
# 更小的结尾意味着未来更容易接上新的数字
tails[left] = num
# tails 的长度就是最长递增子序列的长度
return len(tails)
# --- 使用示例 ---
nums = [10,9,2,4,5,3,7,101,18]
solver = Solution()
print(solver.lengthOfLIS(nums))
5
152. 乘积最大子数组¶
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 请注意，一个只包含一个元素的数组的乘积是这个元素的值。
核心思路：
1.需要保存每一个状态的最大值和最小值，因为最小值更有可能是为负的大数，再乘上一个负数可以变为最大
2.需要记录下目前最大值，与下一刻时刻的最大值进行比较，一直保留全局最大值
class Solution:
def maxProduct(self, nums: List[int]) -> int:
result = max_arr = min_arr = nums[0]
n = len(nums)
for i in range(1, n):
# 记录上一个状态的最大值，否则会被更新覆盖
cur_max = max_arr
max_arr = max(max_arr*nums[i], min_arr*nums[i], nums[i])
min_arr = min(cur_max*nums[i], min_arr*nums[i], nums[i])
result = max(max_arr, result)
return result
nums = [2,3,-2,4]
print(Solution().maxProduct(nums))
6
时间复杂度： 该算法只对数组进行了一次线性扫描，循环中每一步都是常数时间操作。O(n)
空间复杂度： 只使用了有限个变量（result、max_scores、min_scores、num），不依赖于输入规模。O(1)
416. 分割等和子集¶
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
核心思路：
把问题转化为“是否能选出若干数使得和为 sum(nums)/2”的可达性判断。
一维 0/1 背包：dp[0]=True；对每个数 x，倒序更新 s：dp[s] |= dp[s-x]。
结果看 dp[target]。
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
#（1）用 / 2 会得到 float，dp[target] 会报错，必须要用 // ,会得到整数
target = total_sum // 2
dp = [False] * (target + 1)
dp[0] = True
#（2）这里面的物品只能用一次，因此需要先遍历物品，且逆序遍历背包
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]
return dp[target]
nums = [1,5,11,5]
print(Solution().canPartition(nums))
True
时间复杂度： 设数组长度为 n，数组元素和为 S，目标容量为 target = S / 2。
外层循环遍历每一个元素 nums[i]，共 n 次； 内层是一个从 target 逆序到 nums[i] 的循环，最坏情况下需要 target 次。
因此总体时间复杂度为： O(n · target) 也可写为： O(n · (S / 2))，通常简记为 O(n · S)。
空间复杂度： 使用了一维 dp 数组，长度为 target + 1，其余只使用常数额外变量。
空间复杂度为： O(target)，即 O(S)。
32. 最长有效括号¶
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"
核心思路:
把“括号是否匹配”转化为“以当前位置结尾的最优子结构”，并在遇到右括号时，向前跳过已匹配区间寻找对应的左括号。
定义状态： dp[i] 表示 以索引 i 结尾的最长有效括号子串长度。 若 s[i] == '('，则 dp[i] = 0
若 s[i] == ')'，才需要讨论
关键在于：这个右括号 ')' 能不能和前面的某个 '(' 配对。
二、状态转移分两种情况
设当前字符是 s[i] == ')'。
情况 1：前一个字符是 '(' 即形如 "()"，那么：
dp[i] = 2 + dp[i-2]
dp[i-2] 表示在 "()" 之前，是否还能再接一段有效括号。
情况 2：前一个字符是 ')' 即形如 "…))"，需要向前“跳过”一段已经匹配好的括号：
j = i - dp[i-1] - 1
如果 j >= 0 且 s[j] == '('，说明可以匹配：
dp[i] = dp[i-1] + 2 + dp[j-1]
dp[j-1] 用来接上更前面可能存在的有效括号。
from typing import List
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
# dp[i] 表示：以 i 位置字符结尾的「最长连续有效括号子串长度」
# 注意：必须“以 i 结尾”，这是状态定义的关键
dp = [0] * n
# 记录全局最大值
res = 0
# 从 1 开始遍历，因为 i=0 不可能形成有效括号
for i in range(1, n):
# 只有当当前位置是 ')' 时，才可能形成有效括号
if s[i] == ')':
# ------------------------
# 情况 1：形如 "()"
# ------------------------
# 当前是 ')'
# 前一个字符是 '('
# 那么 s[i-1:i+1] = "()"
if s[i-1] == '(':
# "()” 本身贡献 2
# 如果 i >= 2，还需要接上 i-2 位置结尾的有效括号
# 例如："(())" -> dp[3] = dp[1] + 2
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
# ------------------------
# 情况 2：形如 "...))"
# ------------------------
# 这是最难理解、也是最关键的一种情况
else:
# 先解释 dp[i-1] 的含义：
# dp[i-1] 表示：以 i-1 结尾的最长有效括号【长度】
#
# 举例：
# s = "... ( ( ) ) )"
# ^ ^
# i-1 i
#
# dp[i-1] 覆盖的是一整段已经“完全匹配”的括号
# 那么，我们想做的是：
# 在 dp[i-1] 这段「已匹配区间」的前面，
# 看能不能再找到一个 '(' 来和当前 s[i] = ')' 匹配
# i - dp[i-1] 是：那段已匹配区间的起始位置
# 再减 1，就是我们要检查的“候选 '(' 位置”
j = i - dp[i-1] - 1
# 如果 j 合法，且 s[j] == '('
# 说明：
# s[j] 可以和当前 s[i] 这一个 ')' 配对
if j >= 0 and s[j] == '(':
# 先把：
# 1）原本 dp[i-1] 的那一整段有效括号
# 2）新匹配的一对 "()"
# 合在一起
dp[i] = dp[i-1] + 2
# 但这还不够！
# 如果 j > 0，说明在 s[j] 前面，也就是 s[j-1] 位置，还存在一个字符
# 可能还存在一段“更早的有效括号”，因此在dp[i] 的基础上，还要加上 dp[j-1] 的长度
#
# 例如：
# s = "() ( ( ) )"
# ^ j i
#
# dp[j-1] 是可以无缝接在当前结构前面的
if j >= 1:
dp[i] += dp[j-1]
# 更新全局最大值
res = max(res, dp[i])
return res
s = "()(())"
print(Solution().longestValidParentheses(s))
6
from typing import List
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
res = 0
for i in range(1, n):
if s[i] == ')':
# 情况1："()"
if s[i-1] == '(':
dp[i] = (dp[i-2] if i >= 2 else 0) + 2
else:
# 情况2："...))"
j = i - dp[i-1] - 1
if j >= 0 and s[j] == '(':
dp[i] = dp[i-1] + 2
if j >= 1:
dp[i] += dp[j-1]
res = max(res, dp[i])
return res
# 示例
s = "(()())"
print(Solution().longestValidParentheses(s)) # 输出 6
6
时间复杂度： 只遍历字符串一次，每个位置是 O(1) 操作： O(n)
空间复杂度： 使用了一个长度为 n 的 dp 数组： O(n)
背包问题总结：
0/1背包卡哥解读：
完全背包卡哥解读：
动态规划总结：
0/1 背包（每件最多一次）：✅ 先物品，后容量且“逆序”（避免同一轮重复用到当前物品）。
完全背包（可无限次）：要分两类——
求最优值（最大/最小）或求“组合数”（顺序不敏感）：✅ 先物品，后容量且“正序”。
求“排列数”（顺序敏感，如“先放 1 再放 2”和“先放 2 再放 1”算两种）： 先容量，后物品且“正序”。
题型总结¶
动态规划问题可以按照状态结构与依赖关系进行稳定分类。常见算法题基本可以归入以下五类：线性DP、双序列DP、背包DP、区间DP、树形DP。 每一类问题在 状态定义、状态转移、初始化（边界）、遍历顺序 上都有相对固定的模式。掌握这些模式后，大部分DP题都可以快速建模。
一、线性DP（Linear DP）¶
1. 题型特征¶
问题可以按顺序逐步推进，当前位置只依赖前面若干状态。
典型题目：
- 爬楼梯
- 最大子数组
- 打家劫舍
- 买卖股票
2. 状态定义¶
通常定义为：
dp[i] 表示到第 i 个位置时的最优解
示例：
| 题目 | dp含义 |
|---|---|
| 爬楼梯 | dp[i] 到达第i阶的方法数 |
| 最大子数组 | dp[i] 以 i 结尾的最大子数组和 |
| 打家劫舍 | dp[i] 前 i 个房子最大收益 |
3. 状态转移¶
只依赖前几个状态：
dp[i] = f(dp[i-1], dp[i-2], ...)
例如：
爬楼梯
dp[i] = dp[i-1] + dp[i-2]
最大子数组
dp[i] = max(nums[i], dp[i-1] + nums[i])
4. 初始化（边界）¶
线性DP的关键是 最小状态初始化
例如：
爬楼梯
dp[0] = 1
dp[1] = 1
最大子数组
dp[0] = nums[0]
技巧
如果转移涉及 dp[i-1] 或 dp[i-2]，必须保证这些状态存在。
5. 遍历顺序¶
通常：
for i in range(1, n):
因为依赖前面状态。
二、双序列DP（Two Sequence DP）¶
1. 题型特征¶
涉及两个序列（字符串或数组）。
典型题目：
- 最长公共子序列（LCS）
- 编辑距离
- 不同子序列
2. 状态定义¶
dp[i][j]
表示：
text1前i个 与 text2前j个 的问题答案
3. 状态转移¶
例如 LCS：
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
依赖：
dp[i-1][j]
dp[i][j-1]
dp[i-1][j-1]
4. 初始化（DP边界技巧）¶
双序列DP 几乎一定要多开一行一列
dp = [[0]*(n+1) for _ in range(m+1)]
原因：
当 i=0 或 j=0 时表示 空字符串情况
例如：
dp[0][j] = 0
dp[i][0] = 0
对于编辑距离：
dp[i][0] = i
dp[0][j] = j
5. 遍历顺序¶
从小规模到大规模：
for i in range(1, m+1):
for j in range(1, n+1):
因为依赖左、上、左上。
三、背包DP（Knapsack DP）¶
1. 题型特征¶
核心结构：
选择或不选择某个物品
典型题目：
- 0/1背包
- 零钱兑换
- 分割等和子集
2. 状态定义¶
两种形式：
二维
dp[i][j]
表示：
前 i 个物品，容量 j 的最优解
一维优化
dp[j]
表示容量 j 的最优解。
3. 状态转移¶
最大价值： dp[j] = max(dp[j], dp[j-w] + v)
最小物品数：dp[j] = min(dp[j], dp[j-w] + 1)
是否可达：dp[j] = dp[j] or dp[j-w]
方案数量：dp[j] += dp[j-w]
4. 初始化（DP边界）¶
常见技巧：
dp[0] = 1
含义：
容量为0的方案数是1（什么都不选）
例如：
零钱兑换II
dp = [0]*(amount+1)
dp[0] = 1
5. 遍历顺序¶
这是背包DP最重要技巧。
0/1背包
先遍历物品
再倒序遍历容量
for weight,value in items:
for j in range(capacity, weight-1, -1):
防止重复使用。
完全背包
先遍历背包容量
再遍历物品
for j in range(capacity+1):
for weight,value in items:
允许重复使用。
四、区间DP（Interval DP）¶
1. 题型特征¶
问题针对数组或字符串的一个区间。
典型题：
- 最长回文子串
- 戳气球
- 合并石头
2. 状态定义¶
dp[i][j]
表示：
区间 [i,j] 的答案。
3. 状态转移¶
通常通过分割点：
dp[i][j] = min/max(
dp[i][k] + dp[k+1][j]
)
或依赖内部区间：
例如回文串：
dp[i][j] = s[i]==s[j] and dp[i+1][j-1]
4. 初始化（边界）¶
通常：
dp[i][i]
单个元素区间。
例如：
dp[i][i] = True
区间DP 通常不需要额外行列。
5. 遍历顺序¶
必须保证小区间先计算。
常见写法：
for length in range(2, n+1):
for i in range(n):
j = i + length - 1
五、树形DP（Tree DP）¶
1. 题型特征¶
DP状态定义在树节点上。
典型题：
- 打家劫舍III
- 二叉树最大路径和
2. 状态定义¶
通常定义为：
dfs(node) 返回若干状态
例如：
打家劫舍III
[偷当前节点收益, 不偷当前节点收益]
3. 状态转移¶
由左右子树转移：
例如：
rob = node.val + left[1] + right[1]
not_rob = max(left) + max(right)
4. 初始化（边界）¶
叶子节点：
if not node:
return (0,0)
表示空节点收益为0。
5. 遍历顺序¶
必须 后序遍历
原因：
父节点依赖子节点。
六、DP边界问题总结（核心规律）¶
DP边界其实遵循三个原则：
1 字符串DP¶
必须 多开一行一列
dp[m+1][n+1]
避免负索引。
2 组合计数DP¶
必须有：
dp[0] = 1
表示空方案。
3 区间DP¶
初始化：
dp[i][i]
表示最小区间。
4 线性DP¶
初始化最小状态：
dp[0]
dp[1]
七、DP建模统一思考流程¶
遇到DP题时，可以固定按照以下顺序思考：
- 确定题型
线性
双序列
背包
区间
树形
- 定义状态
dp[i]
dp[i][j]
- 写状态转移
找依赖关系。
- 初始化
确定最小子问题。
- 确定遍历顺序
保证依赖先计算。