1 打家劫舍系列
1.1 主线
三题共享同一个决策：当前这个位置，选还是不选
- 选了，就必须跳过与它相邻的位置
- 不选，就继承邻居的最优解
区别只在"相邻"的拓扑长什么样：
| 题 | 相邻结构 | 处理办法 |
|---|---|---|
| 198 | 一条链 | 直接线性 DP |
| 213 | 一个环 | 拆成两条链各做一次 198 |
| 337 | 一棵树 | 后序遍历，每个节点向上返回一对值 |
1.2 打家劫舍
状态定义：
dp[i] = 考虑区间 [0, i] 的房间时，能偷到的最大金额
注意"考虑"两个字 定义是"前 i 间里随便选"，不是"必须偷第 i 间"。所以答案直接是
dp[n-1]，不需要打擂台。这跟后面 300/718 那种"必须以 i 结尾"的定义正好是一对反例，可以拿来对照记。
状态转移：
偷第 i 间： dp[i] = nums[i] + dp[i-2]
不偷第 i 间： dp[i] = dp[i-1]
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
初始化：
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
代码（滚动数组）：
1class Solution:
2 def rob(self, nums: List[int]) -> int:
3 n = len(nums)
4 if n == 1:
5 return nums[0]
6 a, b = nums[0], max(nums[0], nums[1])
7 for i in range(2, n):
8 a, b = b, max(b, a + nums[i])
9 return b
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
1.3 打家劫舍 II
思路: 状态定义与转移完全同 198，唯一的新麻烦是首尾相邻。关键观察：首、尾至多只能偷其中一间（也可能两间都不偷）。于是把环拆成两条链，各跑一次 198，取较大者：
- 情况 A：不考虑最后一间 →
[0, n-2] - 情况 B：不考虑第一间 →
[1, n-1]
代码：
1class Solution:
2 def rob(self, nums: List[int]) -> int:
3 n = len(nums)
4 if n == 1:
5 return nums[0]
6 if n == 2:
7 return max(nums[0], nums[1])
8
9 def cal(l, r):
10 a, b = nums[l], max(nums[l], nums[l + 1])
11 for i in range(l + 2, r):
12 a, b = b, max(b, a + nums[i])
13 return b
14
15 return max(cal(0, n - 1), cal(1, n))
复杂度：
- 时间 O(n)（跑两遍）
- 空间 O(1)
1.4 打家劫舍 III（树形 DP）
状态定义: 每个节点向上返回一个二元组：
rob= 偷了该节点时，以它为根的子树能拿到的最大金额skip= 不偷该节点时，以它为根的子树能拿到的最大金额
状态转移（后序遍历：先拿左右孩子的 (rob, skip)）:
偷node： rob = node.val + lskip + rskip
不偷node：skip = max(lrob, lskip) + max(rrob, rskip)
代码:
1def rob(root) -> int:
2 def dfs(node) -> tuple[int, int]:
3 if not node:
4 return 0, 0 # 空节点：偷不偷都是 0
5 lrob, lskip = dfs(node.left)
6 rrob, rskip = dfs(node.right)
7 rob = node.val + lskip + rskip
8 skip = max(lrob, lskip) + max(rrob, rskip)
9 return rob, skip
10
11 return max(dfs(root))
复杂度：
- 时间 O(n)，每个节点访问一次
- 空间 O(h)，递归栈
2 买卖股票系列
2.1 主线
六道题共享同一个状态骨架：第 i 天结束时，我处在哪个状态。状态无非两类：手上有股票（持有）、手上没股票（不持有）。题目加的每个限制，都只是往这个骨架上再挂一维：
| 题 | 限制 | 状态数 |
|---|---|---|
| 121 | 只能买卖 1 次 | 2 |
| 122 | 不限次数 | 2 |
| 123 | 最多 2 次 | 4（+ 1 个"不操作"） |
| 188 | 最多 k 次 | 2k（+ 1） |
| 309 | 不限次数 + 冷冻期 | 4 |
| 714 | 不限次数 + 手续费 | 2 |
统一编号后 188 就是母题，其余全是特例：
一条贯穿全系列的记忆线 买入 = 减 prices[i]，卖出 = 加 prices[i]，保持 = 继承昨天同一状态。所有转移方程都是这三句话的排列组合。
2.2 买卖股票的最佳时机（只能 1 次）
状态定义:
dp[i][0]：第 i 天结束时持有股票的最大现金dp[i][1]：第 i 天结束时不持有股票的最大现金
状态转移:
dp[i][0] = max(dp[i-1][0], -prices[i]) # 保持 / 今天买入
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) # 保持 / 今天卖出
这题的分水岭在 dp[i][0] 买入写的是
-prices[i]，不是dp[i-1][1] - prices[i]。因为只能交易一次，第一次买入之前的现金必然是 0，不能带着上一轮的利润再买。改成dp[i-1][1] - prices[i]就退化成 122
初始化：dp[0][0] = -prices[0]，dp[0][1] = 0
代码:
1class Solution:
2 def maxProfit(self, prices: List[int]) -> int:
3 n = len(prices)
4 d0, d1 = -prices[0], 0
5 for i in range(1, n):
6 d0, d1 = max(d0, -prices[i]), max(d1, d0 + prices[i])
7 return d1
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
2.3 买卖股票 II（不限次数）
状态定义:
dp[i][0]：第 i 天结束时持有股票的最大现金dp[i][1]：第 i 天结束时不持有股票的最大现金
状态转移（只有买入那行变了）:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) # 可以带着历史利润再买
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
初始化：dp[0][0] = -prices[0]，dp[0][1] = 0
代码：
1class Solution:
2 def maxProfit(self, prices: List[int]) -> int:
3 n = len(prices)
4 d0, d1 = -prices[0], 0
5 for i in range(1, n):
6 d0, d1 = max(d0, d1 - prices[i]), max(d1, d0 + prices[i])
7 return d1
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
2.4 买卖股票 III（最多 2 次）
状态定义（4 个）:
dp[i][0]：第 1 次持有dp[i][1]：第 1 次卖出后不持有dp[i][2]：第 2 次持有dp[i][3]：第 2 次卖出后不持有
状态转移:
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i])
初始化: 考虑定义
dp[0][0] = -prices[0] dp[0][1] = 0
dp[0][2] = -prices[0] dp[0][3] = 0
dp[0][2] = -prices[0] 是什么意思 字面上是"第 0 天完成了买-卖-买三个动作"。现实里这没有收益意义，但作为初值它是合法且不劣的：它保证了第 2 次交易的起点不会被漏掉。DP 初始化只要"不引入非法优势、不遗漏合法路径"就够了，不必句句对应现实动作
代码：
1class Solution:
2 def maxProfit(self, prices: List[int]) -> int:
3 n = len(prices)
4 d0, d1, d2, d3 = -prices[0], 0, -prices[0], 0
5 for i in range(1, n):
6 d0, d1, d2, d3 = max(d0, -prices[i]), max(d1, d0 + prices[i]), max(d2, d1 - prices[i]), max(d3, d2 + prices[i])
7 return d3
答案取 dp[n-1][3] 就够 不用跟
dp[n-1][1]打擂台。因为"只做 1 次交易"完全可以被"第 2 次买了又原价卖"模拟出来，dp[i][3]已经涵盖了交易次数少于 2 的所有情况。
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
2.5 买卖股票 IV（最多 k 次）
状态定义:
把 123 的 4 个状态推广成 2k+1 个，下标 0 … 2k：
0：不操作- 奇数
2j-1：第 j 次持有 - 偶数
2j：第 j 次卖出后不持有
状态转移:
j 为奇数：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])
j 为偶数：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])
初始化：第 0 天，所有奇数列 d[2 * j - 1]= -prices[0], 偶数列d[2 * j] = 0
代码:
1class Solution:
2 def maxProfit(self, k: int, prices: List[int]) -> int:
3 n = len(prices)
4 d = [0] + [-prices[0], 0] * k
5 for i in range(1, n):
6 for j in range(1, k + 1):
7 d[2 * j - 1], d[2 * j] = max(d[2 * j - 1], d[2 * j - 2] - prices[i]), max(d[2 * j], d[2 * j - 1] + prices[i])
8 return d[-1]
复杂度：
- 时间 O(n·k)
- 空间 朴素 O(n·k) / 滚动 O(k)
2.6 买卖股票含冷冻期
状态定义（4 个）:
dp[i][0]：持有股票dp[i][1]：今天卖出（当天刚卖）dp[i][2]：冷冻期（昨天卖的，今天啥也干不了）dp[i][3]：保持卖出（冷冻期已过，空仓待命）
状态转移:
dp[i][0] = max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i-1][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = dp[i-1][1]
dp[i][3] = max(dp[i-1][3], dp[i-1][2])
初始化：dp[0][0] = -prices[0]，其余三个都是 0
答案：max(dp[n-1][1], dp[n-1][2], dp[n-1][3])，最后一天可能停在"刚卖出"、“冷冻中”、“空仓"三种状态的任意一个
代码（滚动数组）：
1class Solution:
2 def maxProfit(self, prices: List[int]) -> int:
3 n = len(prices)
4 d0, d1, d2, d3 = -prices[0], 0, 0, 0
5 for i in range(1, n):
6 d0, d1, d2, d3 = max(d0, d2 - prices[i], d3 - prices[i]), d0 + prices[i], d1, max(d2, d3)
7 return max(d1, d2, d3)
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
2.7 买卖股票含手续费
状态转移（就是 122，卖出时扣一次 fee）:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
初始化：dp[0][0] = -prices[0]，dp[0][1] = 0
fee 扣在买还是卖 扣在卖出（
+ p - fee）或买入（- p - fee）都行，只要一次完整交易只扣一次。扣在卖出更稳妥：扣在买入时，若最后一天仍持有股票，那笔 fee 就白扣了（虽然它不会进入答案）。
代码:
1class Solution:
2 def maxProfit(self, prices: List[int], fee: int) -> int:
3 n = len(prices)
4 d0, d1 = -prices[0], 0
5 for i in range(1, n):
6 d0, d1 = max(d0, d1 - prices[i]), max(d1, d0 + prices[i] - fee)
7 return d1
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
3 子序列 / 子数组系列
3.1 主线
这组题的全部难度都压在状态定义的一句话上，具体是两种写法的抉择：
| 定义写法 | 含义 | 不匹配时 | 答案位置 |
|---|---|---|---|
| 以 i 结尾 | 必须用上第 i 个元素 | 归零 / 重新起步 | 全局打擂台 max(dp) |
| 前 i 个 | 前 i 个里随便挑 | 可以继承邻居 | 表的末尾 dp[n] |
“连续”（子数组）几乎总是逼你用第一种；“可跳过”（子序列）通常允许第二种。先想清楚哪一种，再写转移，顺序反了就会卡住。
3.2 最长递增子序列
状态定义：
dp[i] = 以 nums[i] 结尾的最长递增子序列长度
状态转移：
for j in [0, i-1]:
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
初始化：dp[i] = 1（每个元素自己就是一个长度为 1 的子序列）
返回：max(dp)，不是 dp[-1]
代码（O(n²) 朴素版）：
1def lengthOfLIS(nums: list[int]) -> int:
2 n = len(nums)
3 dp = [1] * n
4 for i in range(1, n):
5 for j in range(i):
6 if nums[j] < nums[i]:
7 dp[i] = max(dp[i], dp[j] + 1)
8 return max(dp)
代码（O(n log n) 贪心 + 二分）：
1def lengthOfLIS(nums: list[int]) -> int:
2 tails = [] # tails[k] = 长度为 k+1 的递增子序列的最小结尾
3 for x in nums:
4 l, r = 0, len(tails) # 找第一个 >= x 的位置（左闭右开）
5 while l < r:
6 mid = (l + r) // 2
7 if tails[mid] >= x:
8 r = mid
9 else:
10 l = mid + 1
11 if l == len(tails):
12 tails.append(x)
13 else:
14 tails[l] = x
15 return len(tails)
复杂度：
- 朴素 O(n²) / O(n)
- 二分版 O(n log n) / O(n)
3.3 最长连续递增序列
状态定义：
dp[i] = 以 nums[i] 结尾的最长连续递增序列长度
状态转移：
if nums[i-1] < nums[i]: dp[i] = dp[i-1] + 1
else: dp[i] = 1
和 300 的唯一差别 “连续"意味着只能接在 i-1 后面，不能回头挑任意的 j。于是内层循环消失，O(n²) 直接降到 O(n)。这个降维的来源不是什么优化技巧，纯粹是题意收紧了转移的来源集合。
初始化：全部 dp[i] = 1
返回：max(dp)
代码（朴素版 + 滚动版）：
1def findLengthOfLCIS(nums: list[int]) -> int: # 朴素
2 n = len(nums)
3 dp = [1] * n
4 for i in range(1, n):
5 if nums[i - 1] < nums[i]:
6 dp[i] = dp[i - 1] + 1
7 return max(dp)
8
9
10def findLengthOfLCIS(nums: list[int]) -> int: # 滚动
11 ans = cur = 1
12 for i in range(1, len(nums)):
13 cur = cur + 1 if nums[i - 1] < nums[i] else 1
14 ans = max(ans, cur)
15 return ans
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
3.4 最大子数组和
状态定义:
dp[i] = 以 nums[i] 结尾的最大子数组和
状态转移:
接上前面：dp[i] = dp[i-1] + nums[i]
另起炉灶：dp[i] = nums[i]
dp[i] = max(dp[i-1] + nums[i], nums[i])
初始化：dp[0] = nums[0]
返回：max(dp)
一句话理解转移 如果
dp[i-1] <= 0，它对后面只有拖累，果断丢掉从nums[i]重开。这就是 Kadane 算法，和贪心版本"和一旦为负就清零"是同一件事的两种说法。
代码（朴素版 + 滚动版）:
1def maxSubArray(nums: list[int]) -> int: # 朴素
2 n = len(nums)
3 dp = [0] * n
4 dp[0] = nums[0]
5 for i in range(1, n):
6 dp[i] = max(dp[i - 1] + nums[i], nums[i])
7 return max(dp)
8
9
10def maxSubArray(nums: list[int]) -> int: # 滚动
11 cur = ans = nums[0]
12 for x in nums[1:]:
13 cur = max(cur + x, x)
14 ans = max(ans, cur)
15 return ans
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
3.5 乘积最大子数组
状态定义:
fmax[i]：以nums[i]结尾的连续子数组的最大乘积fmin[i]：以nums[i]结尾的连续子数组的最小乘积
为什么要维护最小值 乘法与加法的关键区别：负负得正。当前最小值（很大的负数）乘上一个负数，可能瞬间变成最大值。只维护
fmax会丢掉这条路径。 反例：[-2, 3, -4]，正确答案是(-2)·3·(-4) = 24。只维护最大值走到-4时，前面最大是 3，3·(-4) = -12，丢掉了-6·(-4) = 24。
状态转移:
fmax[i] = max(fmax[i-1] * x, fmin[i-1] * x, x)
fmin[i] = min(fmax[i-1] * x, fmin[i-1] * x, x)
其中 x = nums[i]。三者取 max/min 中的 x 对应"从当前位置重新开始”。
滚动变量的覆盖陷阱
fmin的转移需要旧的fmax。如果先更新fmax再算fmin，用的就是新值，结果会错。解决方法：用 Python 元组同时赋值，右边整体求值后再赋给左边。
初始化：fmax = fmin = nums[0]，ans = nums[0]
返回：ans（全局打擂台）
代码（方法一：元组同时赋值）:
1class Solution:
2 def maxProduct(self, nums: List[int]) -> int:
3 ans = fmax = fmin = nums[0]
4 for x in nums[1:]:
5 fmax, fmin = (
6 max(fmax * x, fmin * x, x),
7 min(fmax * x, fmin * x, x),
8 )
9 ans = max(ans, fmax)
10 return ans
代码（方法二：遇负交换）:
1class Solution:
2 def maxProduct(self, nums: List[int]) -> int:
3 ans = fmax = fmin = nums[0]
4 for x in nums[1:]:
5 if x < 0:
6 fmax, fmin = fmin, fmax
7 fmax = max(x, fmax * x)
8 fmin = min(x, fmin * x)
9 ans = max(ans, fmax)
10 return ans
两种写法的等价性 方法二在
x < 0时先交换fmax/fmin，这样后续max/min的含义就和x > 0时一致了：乘以（交换后的）大值得大值。本质是把三路 max 里的分类讨论提前做掉。
复杂度：
- 时间 O(n)
- 空间 O(1)
3.6 最长有效括号
状态定义:
dp[i] = 以 s[i] 结尾的最长有效括号子串的长度
以 ( 结尾的一定是 0，只需处理 s[i] == ')'。
状态转移（分两种情况）:
情况 1：s[i-1] == '('，形如 ...()
dp[i] = dp[i-2] + 2
直接和前一个 ( 配对，再拼上 dp[i-2]（前面可能紧邻的有效串）。
情况 2：s[i-1] == ')'，形如 ...))
先跳过内部已匹配的 dp[i-1] 长度，看 s[i - dp[i-1] - 1] 是否为 (：
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
三部分：内部已匹配长度 + 当前这对 + 再往前拼接的有效串。
边界检查 情况 1 需要
i >= 2才能访问dp[i-2]；情况 2 需要i - dp[i-1] - 1 >= 0和i - dp[i-1] - 2 >= 0。越界时对应的 dp 值视为 0。
初始化：dp = [0] * n，全零
返回：填表过程中打擂台取全局 max
代码（DP）:
1class Solution:
2 def longestValidParentheses(self, s: str) -> int:
3 n = len(s)
4 dp = [0] * n
5 res = 0
6 for i in range(1, n):
7 if s[i] == ')':
8 if s[i - 1] == '(':
9 dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
10 elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(':
11 dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] - 2 >= 0 else 0)
12 res = max(res, dp[i])
13 return res
代码（栈）:
栈底始终放"最后一个未匹配右括号的下标”，作为有效子串的左边界分隔点。初始压入 -1 作为哨兵；遇 ( 压下标；遇 ) 弹栈顶，栈非空则 i - stack[-1] 是当前有效长度，栈空则压入 i 作为新分隔点。
1class Solution:
2 def longestValidParentheses(self, s: str) -> int:
3 stack = [-1]
4 res = 0
5 for i, c in enumerate(s):
6 if c == '(':
7 stack.append(i)
8 else:
9 stack.pop()
10 if stack:
11 res = max(res, i - stack[-1])
12 else:
13 stack.append(i)
14 return res
栈 vs DP 对比 两种方法时空复杂度相同。栈的思路更直觉（分隔点天然处理了拼接），DP 的转移方程更显式（面试时容易讲清每一步的来源）。推荐两种都掌握。
复杂度：
- 时间 O(n)
- 空间 O(n)
3.7 最长重复子数组
状态定义:
dp[i][j] = 以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度，表的尺寸 (m+1) × (n+1)
状态转移：
nums1[i-1] == nums2[j-1] ：dp[i][j] = dp[i-1][j-1] + 1
不相等 ：dp[i][j] = 0
初始化：全 0（第 0 行 / 第 0 列表示"空数组"，长度自然为 0）
返回：填表过程中打擂台取全局 max
代码（朴素版）：
1def findLength(nums1: list[int], nums2: list[int]) -> int:
2 m, n = len(nums1), len(nums2)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 ans = 0
5 for i in range(1, m + 1):
6 for j in range(1, n + 1):
7 if nums1[i - 1] == nums2[j - 1]:
8 dp[i][j] = dp[i - 1][j - 1] + 1
9 ans = max(ans, dp[i][j])
10 return ans
代码（滚动数组，一维）：
1def findLength(nums1: list[int], nums2: list[int]) -> int:
2 m, n = len(nums1), len(nums2)
3 dp = [0] * (n + 1)
4 ans = 0
5 for i in range(1, m + 1):
6 for j in range(n, 0, -1): # 必须倒序
7 dp[j] = dp[j - 1] + 1 if nums1[i - 1] == nums2[j - 1] else 0
8 ans = max(ans, dp[j])
9 return ans
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
3.8 最长公共子序列
状态定义
dp[i][j] = text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列长度
状态转移:
text1[i-1] == text2[j-1] ：dp[i][j] = dp[i-1][j-1] + 1
不相等 ：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 不匹配时的两个候选分别对应"扔掉 text1 的第 i 个字符"和"扔掉 text2 的第 j 个字符"。
初始化：全 0
返回：dp[m][n]
代码（朴素版）：
1def longestCommonSubsequence(text1: str, text2: str) -> int:
2 m, n = len(text1), len(text2)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 for i in range(1, m + 1):
5 for j in range(1, n + 1):
6 if text1[i - 1] == text2[j - 1]:
7 dp[i][j] = dp[i - 1][j - 1] + 1
8 else:
9 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
10 return dp[m][n]
代码（滚动数组，一维）：
1def longestCommonSubsequence(text1: str, text2: str) -> int:
2 m, n = len(text1), len(text2)
3 dp = [0] * (n + 1)
4 for i in range(1, m + 1):
5 prev = 0 # prev = dp[i-1][j-1]
6 for j in range(1, n + 1):
7 tmp = dp[j] # 存下 dp[i-1][j]，给下一轮当左上角
8 if text1[i - 1] == text2[j - 1]:
9 dp[j] = prev + 1
10 else:
11 dp[j] = max(dp[j], dp[j - 1]) # dp[j] 是上一行，dp[j-1] 是本行
12 prev = tmp
13 return dp[n]
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
3.9 不相交的线
思路：完全等价于 1143。 连线不能相交 ⟺ 被连的元素在两个数组里相对顺序一致 ⟺ 它们构成一个公共子序列。 所以问题就是"最长公共子序列有多长"，代码原封不动搬 1143，只把字符换成数字。
1def maxUncrossedLines(nums1: list[int], nums2: list[int]) -> int:
2 m, n = len(nums1), len(nums2)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 for i in range(1, m + 1):
5 for j in range(1, n + 1):
6 if nums1[i - 1] == nums2[j - 1]:
7 dp[i][j] = dp[i - 1][j - 1] + 1
8 else:
9 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
10 return dp[m][n]
复杂度：
- 时间 O(m·n)
- 空间 O(m·n)（滚动同 1143，O(n)）
4 双串编辑操作系列
4.1 主线
接着 1143 往下走，这四题的表格骨架、下标偏移、遍历顺序和 1143 一模一样，唯一变化的是：题目允许你做哪些操作。允许的操作越多，dp[i][j] 能从越多的格子转移过来。
状态定义都是同一句话的变体：
dp[i][j] = 只看 s 的前 i 个和 t 的前 j 个字符时，某个量的最优值 / 计数 / 真假
转移永远在问同一件事：s[i-1] 和 t[j-1] 这一对末尾字符怎么处理。相等就白拿一格斜线，不等就看被允许往哪些方向退：
| 题 | 允许的操作 | 不等时能退到哪 |
|---|---|---|
| 392 | 只能删 t | 左 dp[i][j-1] |
| 115 | 只能删 s（且是计数） | 上 dp[i-1][j] |
| 583 | s、t 都能删 | 上、左，取 min +1 |
| 72 | 删、增、改 | 上、左、左上，取 min +1 |
4.2 判断子序列
状态定义:
dp[i][j] = s 的前 i 个字符是否是 t 的前 j 个字符的子序列（布尔值），表的尺寸 (m+1) × (n+1)
状态转移:
s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] # 配上了，两边同时退一格
不相等 ：dp[i][j] = dp[i][j-1] # 只能删 t 的这个字符
为什么没有
dp[i-1][j]这条路 删 s 的字符 = 放弃 s 里的某个字符不去匹配，可 s 必须整个被匹配上才叫子序列。所以 s 这一侧的下标只能在"配上了"的时候前进，不能主动跳过。这是 392 与 1143 的唯一差别：LCS 两边都能跳，392 只有 t 能跳。
初始化：
dp[0][j] = True (j ∈ [0, n]) 空串是任何串的子序列
dp[i][0] = False (i ≥ 1) 非空串不可能是空串的子序列
dp[i][j] = False
返回：dp[m][n]
代码（朴素版）：
1class Solution:
2 def isSubsequence(self, s: str, t: str) -> bool:
3 m, n = len(s), len(t)
4 dp = [[False] * (n + 1) for _ in range(m + 1)]
5 for j in range(n + 1):
6 dp[0][j] = True
7 for i in range(1, m + 1):
8 for j in range(1, n + 1):
9 if s[i - 1] == t[j - 1]:
10 dp[i][j] = dp[i - 1][j - 1]
11 else:
12 dp[i][j] = dp[i][j - 1]
13 return dp[m][n]
代码（双指针，本题的实际最优解）：
1class Solution:
2 def isSubsequence(self, s: str, t: str) -> bool:
3 i = 0
4 for ch in t:
5 if i < len(s) and s[i] == ch:
6 i += 1
7 return i == len(s)
复杂度：
- 时间 DP O(m·n) / 双指针 O(m+n)
- 空间 朴素 O(m·n) / 滚动 O(n) / 双指针 O(1)
4.3 不同的子序列
状态定义:
dp[i][j] = 在 s 的前 i 个字符中，能凑出 t 的前 j 个字符的方案数
“前 i 个"是前缀，挑出来的才是子序列 i 限定的是在哪个前缀范围内挑，挑出来的字符不要求连续。这跟 718 那种"子数组"是两码事。
状态转移:
s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
不相等 ：dp[i][j] = dp[i-1][j]
初始化：
dp[i][0] = 1 (i ∈ [0, m]) t 是空串：把 s 全删光，恰好 1 种方案
dp[0][j] = 0 (j ≥ 1) s 是空串却要凑出非空的 t：0 种
返回：dp[m][n]
代码（朴素版）：
1class Solution:
2 def numDistinct(self, s: str, t: str) -> int:
3 m, n = len(s), len(t)
4 dp = [[0] * (n + 1) for _ in range(m + 1)]
5 for i in range(m + 1):
6 dp[i][0] = 1
7
8 for i in range(1, m + 1):
9 for j in range(1, n + 1):
10 if s[i - 1] == t[j - 1]:
11 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
12 else:
13 dp[i][j] = dp[i - 1][j]
14 return dp[m][n]
代码（滚动数组，一维）：
1class Solution:
2 def numDistinct(self, s: str, t: str) -> int:
3 n = len(t)
4 dp = [1] + [0] * n
5 for ch in s:
6 for j in range(n, 0, -1): # 必须倒序
7 if ch == t[j - 1]:
8 dp[j] += dp[j - 1]
9 return dp[n]
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
4.4 两个字符串的删除操作
状态定义:
dp[i][j] = 让 s 的前 i 个与 t 的前 j 个变得相同，所需的最少删除次数（两个串都能删）
状态转移:
相等： dp[i][j] = dp[i-1][j-1] # 末尾天然对上，不花步数
不相等：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 # 删 s[i-1] 或删 t[j-1]
初始化：
dp[i][0] = i 另一串为空，只能把这一串全删掉
dp[0][j] = j
返回：dp[m][n]
代码（朴素版）：
1class Solution:
2 def minDistance(self, word1: str, word2: str) -> int:
3 m, n = len(word1), len(word2)
4 dp = [[0] * (n + 1) for _ in range(m + 1)]
5 for i in range(m + 1):
6 dp[i][0] = i
7 for j in range(n + 1):
8 dp[0][j] = j
9
10 for i in range(1, m + 1):
11 for j in range(1, n + 1):
12 if word1[i - 1] == word2[j - 1]:
13 dp[i][j] = dp[i - 1][j - 1]
14 else:
15 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1
16 return dp[m][n]
代码（滚动数组，一维）：
1class Solution:
2 def minDistance(self, word1: str, word2: str) -> int:
3 m, n = len(word1), len(word2)
4 dp = list(range(n + 1)) # 第 0 行：dp[0][j] = j
5 for i in range(1, m + 1):
6 prev = dp[0] # prev = dp[i-1][j-1]
7 dp[0] = i # dp[i][0] = i
8 for j in range(1, n + 1):
9 tmp = dp[j]
10 if word1[i - 1] == word2[j - 1]:
11 dp[j] = prev
12 else:
13 dp[j] = min(dp[j], dp[j - 1]) + 1 # dp[j] 上一行，dp[j-1] 本行
14 prev = tmp
15 return dp[n]
另一条路：直接用 1143 删除次数 = 两串各自删到只剩公共子序列：
1return len(word1) + len(word2) - 2 * lcs(word1, word2)
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
4.5 编辑距离
状态定义:
dp[i][j] = 把 s 的前 i 个字符转换成 t 的前 j 个字符，所需的最少操作数（增、删、改各算一步）
状态转移:
相等： dp[i][j] = dp[i-1][j-1]
不相等：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
推导的统一姿势：假设最后一步做了某个操作，做完之后剩下的是哪个子问题？
| 最后一步做什么 | 做完之后还剩什么 | 式子 |
|---|---|---|
删掉 s[i-1] | s 前 i−1 个 ⇒ t 前 j 个 | dp[i-1][j] + 1 |
在 s 末尾插入 t[j-1] | 这一对已配平，剩 s 前 i 个 ⇒ t 前 j−1 个 | dp[i][j-1] + 1 |
把 s[i-1] 改成 t[j-1] | 这一对当场配平，剩 s 前 i−1 个 ⇒ t 前 j−1 个 | dp[i-1][j-1] + 1 |
初始化：
dp[i][0] = i (i ∈ [0, m]) t 是空串：把 s 的 i 个字符全删掉
dp[0][j] = j (j ∈ [0, n]) s 是空串：插入 t 的 j 个字符
返回：dp[m][n]
代码（朴素版）：
1class Solution:
2 def minDistance(self, word1: str, word2: str) -> int:
3 m, n = len(word1), len(word2)
4 dp = [[0] * (n + 1) for _ in range(m + 1)]
5 for i in range(m + 1):
6 dp[i][0] = i
7 for j in range(n + 1):
8 dp[0][j] = j
9 for i in range(1, m + 1):
10 for j in range(1, n + 1):
11 if word1[i - 1] == word2[j - 1]:
12 dp[i][j] = dp[i - 1][j - 1]
13 else:
14 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
15 return dp[m][n]
代码（滚动数组，一维）：
1class Solution:
2 def minDistance(self, word1: str, word2: str) -> int:
3 m, n = len(word1), len(word2)
4 dp = list(range(n + 1))
5 for i in range(1, m + 1):
6 prev = dp[0] # prev = dp[i-1][j-1]
7 dp[0] = i
8 for j in range(1, n + 1):
9 tmp = dp[j] # 存下 dp[i-1][j]，下一轮当左上角
10 if word1[i - 1] == word2[j - 1]:
11 dp[j] = prev
12 else:
13 dp[j] = min(dp[j], dp[j - 1], prev) + 1
14 prev = tmp
15 return dp[n]
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
5 回文系列
5.1 主线
前面四章的表都是"两个串各拿一个前缀”，这一章换成一个串、两个端点：
dp[i][j] 描述的是区间 s[i..j]，i 是左端点、j 是右端点。
这类表有三个共同点：
- 只有上三角有意义：
i > j的格子代表"左端点跑到右端点右边"，无意义 - 对角线是种子：
dp[i][i]对应单个字符，回文性 True、长度 1 - 转移都要读
dp[i+1][j-1]：掐掉两头后的内层区间
这一章唯一的新东西就是遍历顺序
dp[i+1][j-1]在当前格的左下方，所以必须 i 从下往上（倒序）、j 从左往右（正序，且从 j = i 起步）。 前面所有双串 DP 的来源都在上方 / 左方，所以 i、j 都正序——顺序不是背下来的，画一格看它依赖谁，方向就定了。
三题的差别只在"表里存什么"：
| 题 | dp 存什么 | 不等时 |
|---|---|---|
| 647 | 区间是不是回文（布尔） | False，没有退路 |
| 5 | 同 647，额外记录最长的那段边界 | False |
| 516 | 区间里最长回文子序列的长度 | max(下, 左)，两条退路 |
5.2 回文子串
状态定义:
dp[i][j] = 子串 s[i..j] 是否是回文串（布尔值），表的尺寸 n × n
状态转移:
s[i]与s[j]不等时直接 False- 相等时还要看中间剩了什么：
i == j ：dp[i][j] = True 单个字符
j - i == 1：dp[i][j] = True "aa"，中间空无一物
j - i > 1 ：dp[i][j] = dp[i+1][j-1] 中间那段说了算
合并成一行：
if s[i] == s[j] and (j - i <= 1 or dp[i+1][j-1]):
dp[i][j] = True
ans += 1
初始化：全 False
遍历顺序：i 从 n-1 到 0，j 从 i 到 n-1
返回：计数 ans
代码（区间 DP）：
1class Solution:
2 def countSubstrings(self, s: str) -> int:
3 n = len(s)
4 dp = [[False] * n for _ in range(n)]
5 ans = 0
6 for i in range(n - 1, -1, -1): # i 倒序
7 for j in range(i, n): # j 从 i 起，只填上三角
8 if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):
9 dp[i][j] = True
10 ans += 1
11 return ans
代码（中心扩散，空间 O(1)）：
1class Solution:
2 def countSubstrings(self, s: str) -> int:
3 n, ans = len(s), 0
4 for c in range(2 * n - 1): # 2n-1 个中心：n 个字符 + n-1 个缝隙
5 l, r = c // 2, c // 2 + c % 2
6 while l >= 0 and r < n and s[l] == s[r]:
7 ans += 1
8 l -= 1
9 r += 1
10 return ans
复杂度：
- 时间 O(n²)
- 空间 DP O(n²) / 中心扩散 O(1)
5.3 最长回文子串
思路：和 647 是同一张表、同一套转移、同一个遍历顺序，只是统计口径换了：647 数有多少个 True，本题记录哪个 True 对应的区间最长。
状态定义:
dp[i][j] = 子串 s[i..j] 是否是回文串
状态转移：同 647
初始化：全 False
返回：用 ans、l、r 记录最长那段的长度和左右端点，最后切片 s[l:r+1]
代码（区间 DP）：
1class Solution:
2 def longestPalindrome(self, s: str) -> str:
3 n = len(s)
4 dp = [[False] * n for _ in range(n)]
5 ans = l = r = 0
6 for i in range(n - 1, -1, -1):
7 for j in range(i, n):
8 if s[i] == s[j] and (j - i <= 1 or dp[i + 1][j - 1]):
9 dp[i][j] = True
10 if j - i + 1 > ans:
11 ans = j - i + 1
12 l, r= i, j
13
14 return s[l:r + 1]
代码（中心扩散）：
1class Solution:
2 def longestPalindrome(self, s: str) -> str:
3 n = len(s)
4 start, length = 0, 1
5 for c in range(2 * n - 1):
6 l, r = c // 2, c // 2 + c % 2
7 while l >= 0 and r < n and s[l] == s[r]:
8 if r - l + 1 > length:
9 start, length = l, r - l + 1
10 l -= 1
11 r += 1
12 return s[start:start + length]
复杂度：
- 时间 O(n²)
- 空间 DP O(n²) / 中心扩散 O(1)
5.4 最长回文子序列
状态定义:
dp[i][j] = 区间 s[i..j] 内最长回文子序列的长度
状态转移:
s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2 两头必然能当最外层，白拿 2
s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1]) 两头留不住，扔一个
初始化：dp[i][i] = 1（单个字符自成长度 1 的回文），其余 0
遍历顺序：i 从 n-1 到 0，j 从 i+1 到 n-1
返回：dp[0][n-1]，整个串这个最大区间的答案
代码：
1class Solution:
2 def longestPalindromeSubseq(self, s: str) -> int:
3 n = len(s)
4 dp = [[0] * n for _ in range(n)]
5 for i in range(n - 1, -1, -1):
6 dp[i][i] = 1 # 对角线顺手填，不必单开一层循环
7 for j in range(i + 1, n):
8 if s[i] == s[j]:
9 dp[i][j] = dp[i + 1][j - 1] + 2
10 else:
11 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
12 return dp[0][n - 1]
复杂度：
- 时间 O(n²)
- 空间 O(n²)
6 递推入门系列
6.1 斐波那契数
状态定义:
dp[i] = 第 i 个斐波那契数
状态转移:
dp[i] = dp[i-1] + dp[i-2]
初始化：
dp[0] = 0
dp[1] = 1
返回：dp[n]
代码（滚动数组）：
1class Solution:
2 def fib(self, n: int) -> int:
3 if n < 2:
4 return n
5 a, b = 0, 1
6 for _ in range(2, n + 1):
7 a, b = b, a + b
8 return b
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
6.2 爬楼梯
状态定义:
dp[i] = 爬到第 i 阶的方法总数
状态转移:
dp[i] = dp[i-1] + dp[i-2]
└ 从 i-1 迈一步 └ 从 i-2 迈两步
初始化：
dp[1] = 1 一阶：只有 1 种
dp[2] = 2 两阶：1+1 或 2
返回：dp[n]
代码（滚动数组）：
1class Solution:
2 def climbStairs(self, n: int) -> int:
3 a, b = 1, 1 # dp[0], dp[1]
4 for _ in range(n - 1):
5 a, b = b, a + b
6 return b
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
6.3 使用最小花费爬楼梯
状态定义:
dp[i] = 站上第 i 阶所需的最低花费
花的是"出发那一阶"的钱
cost[i]的含义是从第 i 阶往上迈要付的费用，不是"落在第 i 阶"要付的费用。所以站上某一阶本身不花钱，dp[0] = dp[1] = 0。 这个方向一旦搞反，转移就会写成dp[i-1] + cost[i]，答案整体偏一格。
状态转移:
dp[i] = min( dp[i-1] + cost[i-1], dp[i-2] + cost[i-2] )
└ 从 i-1 迈一步 └ 从 i-2 迈两步
初始化：dp[0] = dp[1] = 0（题目允许从第 0 或第 1 阶起步）
返回：dp[n]
cost 有 n 个，dp 要开 n+1 个 楼顶是第 n 阶，它没有
cost[n]——因为没人需要从楼顶再往上迈。dp 数组长度是n+1，下标0 … n，答案在dp[n]。
代码（滚动数组）：
1class Solution:
2 def minCostClimbingStairs(self, cost: List[int]) -> int:
3 n = len(cost)
4 a, b = 0, 0 # dp[0], dp[1]
5 for i in range(2, n + 1):
6 a, b = b, min(b + cost[i - 1], a + cost[i - 2])
7 return b
复杂度：
- 时间 O(n)
- 空间 朴素 O(n) / 滚动 O(1)
6.4 杨辉三角
状态定义:
res[i][j] = 第 i 行第 j 个元素的值（0-indexed）
状态转移:
res[i][j] = res[i-1][j-1] + res[i-1][j] (1 <= j <= i-1)
两端 j = 0 和 j = i 恒为 1。
初始化：每行先全填 1，再用转移方程覆盖中间位置
返回：res
代码:
1class Solution:
2 def generate(self, numRows: int) -> List[List[int]]:
3 res = []
4 for i in range(numRows):
5 row = [1] * (i + 1)
6 for j in range(1, i):
7 row[j] = res[-1][j - 1] + res[-1][j]
8 res.append(row)
9 return res
滚动数组 如果只需要第 n 行（119 题），可以只维护一行，从右往左更新（避免覆盖左邻）：
1row = [1] * (n + 1) 2for i in range(2, n + 1): 3 for j in range(i - 1, 0, -1): 4 row[j] += row[j - 1]这和 01 背包倒序遍历是完全同构的。
复杂度：
- 时间 O(n²)，空间 O(n²)（存储所有行）；只要第 n 行则空间 O(n)
7 网格路径系列
7.1 主线
三题共用同一张 m × n 的网格表，也共用同一句话：只能向右、向下走，所以每个格子的来源只有上方和左方。
| 题 | dp[i][j] 含义 | 转移 |
|---|---|---|
| 62 | 到达 (i,j) 的路径数 | dp[i-1][j] + dp[i][j-1] |
| 63 | 同上，但有障碍 | 同 62；障碍处直接 0 |
| 64 | 到达 (i,j) 的最小路径和 | min(dp[i-1][j], dp[i][j-1]) + grid[i][j] |
7.2 不同路径
状态定义:
dp[i][j] = 从起点走到 (i,j) 的不同路径总数
状态转移:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化：第一行、第一列全为 1（只能一路向右 / 一路向下，各只有一种走法）
遍历顺序：从上往下，从左往右
返回：dp[m-1][n-1] or dp[-1][-1]
代码（一维滚动）：
1class Solution:
2 def uniquePaths(self, m: int, n: int) -> int:
3 dp = [1] * n # 第一行
4 for i in range(1, m):
5 for j in range(1, n): # j 从 1 开始，j = 0 那列恒为 1
6 dp[j] += dp[j - 1]
7 return dp[-1]
内层从
j = 1起，不是j = 2j = 0那一列是第一列，恒为 1，不参与递推（它没有左邻居）；从j = 1开始才对。手稿写的j > 1会漏掉第二列。
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
7.3 不同路径 II
思路：转移与 62 完全一致，只多一条规则，障碍格的路径数是 0
状态转移:
grid[i][j] == 1：dp[i][j] = 0
否则 ：dp[i][j] = dp[i-1][j] + dp[i][j-1]
初始化：
第一行：从左往右填 1，碰到障碍立刻 break（它右边的全是 0）
第一列：从上往下填 1，碰到障碍立刻 break（它下面的全是 0）
返回：dp[m-1][n-1]
代码（一维滚动）：
1class Solution:
2 def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
3 if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
4 return 0
5 m, n = len(obstacleGrid), len(obstacleGrid[0])
6 dp = [0] * n
7 for j in range(n):
8 if obstacleGrid[0][j] == 0:
9 dp[j] = 1
10 else:
11 break
12
13 for i in range(1, m):
14 for j in range(n):
15 if obstacleGrid[i][j] == 1:
16 dp[j] = 0
17 elif j > 0:
18 dp[j] += dp[j - 1]
19 return dp[-1]
一维版里第一列是怎么被处理的
j = 0时既不清零也不累加，dp[0]就保持上一行的值——正是"第一列只能从上面下来"的语义；而一旦某行的grid[i][0]是障碍，dp[0]会被清零并一直传下去。第一列的初始化被这两条自动兜住了，不用单独写一遍。
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
7.4 最小路径和
状态定义:
dp[i][j] = 从起点走到 (i,j) 的最小路径和
状态转移:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
初始化：第一行、第一列是前缀和（只有一条路可走，把沿途的值累加起来）
返回：dp[m-1][n-1]
代码（一维滚动）：
1class Solution:
2 def minPathSum(self, grid: List[List[int]]) -> int:
3 m, n = len(grid), len(grid[0])
4 dp = [0] * n
5 dp[0] = grid[0][0]
6 for j in range(1, n): # 第一行前缀和
7 dp[j] = dp[j - 1] + grid[0][j]
8 for i in range(1, m):
9 dp[0] += grid[i][0] # 第一列只能从上面下来
10 for j in range(1, n):
11 dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
12 return dp[-1]
代码（哨兵版，省掉边界初始化）：
1class Solution:
2 def minPathSum(self, grid: List[List[int]]) -> int:
3 m, n = len(grid), len(grid[0])
4 INF = float('inf')
5 dp = [[INF] * (n + 1) for _ in range(m + 1)]
6 dp[0][1] = 0 # 只开一个口子当起点的"上方"
7 for i in range(1, m + 1):
8 for j in range(1, n + 1):
9 dp[i][j] = grid[i - 1][j - 1] + min(dp[i - 1][j], dp[i][j - 1])
10 return dp[m][n]
哨兵那一格为什么是
dp[0][1] = 0把表扩成(m+1) × (n+1)、全填 INF，越界方向就自动"走不通"（INF 永远不会被 min 选中），于是第一行第一列的前缀和不用手写了。 但必须留一个入口：起点(1,1)的两个来源dp[0][1]和dp[1][0]若都是 INF，起点就永远到不了。任选其一置 0 即可（dp[1][0] = 0等价）。 这个技巧只对求最小值的题好用；62 那种求计数的题，哨兵应该填 0 而不是 INF。
复杂度：
- 时间 O(m·n)
- 空间 朴素 O(m·n) / 滚动 O(n)
8 拆分与计数系列
8.1 主线
dp 的下标不再是坐标，而是规模（数字 i 本身、节点个数 i）。枚举一个分割点，把规模 i 拆成两个更小的子问题。
| 题 | dp[i] 含义 | 枚举什么 | 合并方式 |
|---|---|---|---|
| 343 | 拆分 i 得到的最大乘积 | 第一个数 j | 乘 |
| 96 | i 个节点的 BST 形状数 | 谁当根 | 左右相乘再求和 |
8.2 整数拆分
状态定义:
dp[i] = 把 i 拆成至少两个正整数之和后，各数乘积的最大值
状态转移:
枚举拆出来的第一个数 j，剩下的 i - j 有两种命运：
i-j 不再拆：j × (i - j)
i-j 继续拆：j × dp[i - j]
dp[i] = max(dp[i], j × (i - j), j × dp[i - j]) j = 1 … i//2
两条分支缺一不可 只写
j × dp[i-j]会漏掉"恰好拆成两个数"的情况，而它常常就是最优解（比如dp[4] = 2 × 2）。 因为dp[i-j]的定义是"至少拆成两个数"，它压根不包含"i-j保持原样"这种可能。转移里出现的每个 dp 值，都要回头核对它的定义包不包含你现在需要的情况。
初始化：dp[2] = 1（2 = 1 + 1），其余 0
返回：dp[n]
代码（朴素版）：
1class Solution:
2 def integerBreak(self, n: int) -> int:
3 dp = [0] * (n + 1)
4 dp[2] = 1
5 for i in range(3, n + 1):
6 for j in range(1, i // 2 + 1):
7 dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
8 return dp[n]
8.2.1 内层优化：j 其实只需要 2 和 3
推导链条：
- 算出前几项
dp[1..5] = 1, 1, 2, 4, 6，可以看出 i ≥ 4 时dp[i] ≥ i（大数拆开只会更大） - 所以拆出的因子越大越不划算，j 只需要试 1、2、3
j = 1时dp[i] = 1 × dp[i-1] = dp[i-1]，乘个 1 不产生任何新价值，可以丢掉- 于是只剩：
dp[i] = max(2 × dp[i-2], 3 × dp[i-3])
这一步要连带改定义：上式里的 dp[i-2]、dp[i-3] 必须允许"不拆"，否则 dp[4] = 2 × dp[2] = 2 × 1 = 2 就错了。所以把定义放宽成：
dp[i] = i 自身与 i 的所有拆分乘积中的最大值（允许不拆）
对应初始化改成 dp[1] = 1, dp[2] = 2, dp[3] = 3
定义放宽之后，n ≤ 3 必须特判 新定义下
dp[2] = 2、dp[3] = 3，但题目要求至少拆成两个数，正确答案是1和2。所以n ≤ 3时直接return n - 1，从i = 4起才用递推。 这是优化版最容易翻车的地方：为了递推方便改了定义，就要检查改动有没有污染边界的答案。
代码（优化版）：
1class Solution:
2 def integerBreak(self, n: int) -> int:
3 if n <= 3:
4 return n - 1
5 dp = [0, 1, 2, 3] + [0] * (n - 3) # 放宽定义：允许不拆
6 for i in range(4, n + 1):
7 dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])
8 return dp[n]
8.2.2 数学解法：尽量拆 3
由上面的分析可知，最优拆分里只会出现 2 和 3。设有 m 个 2、k 个 3，则 n = 2m + 3k。而 2 + 2 + 2 = 3 + 3，但 2³ = 8 < 3² = 9，三个 2 不如两个 3，所以 2 最多留两个。
于是按 n % 3 分三类：
r == 0：ans = 3^q
r == 1：ans = 3^(q-1) × 4 # 借一个 3 出来，3+1 拆成 2+2 更优
r == 2：ans = 3^q × 2
代码（数学版）：
1class Solution:
2 def integerBreak(self, n: int) -> int:
3 if n <= 3:
4 return n - 1
5 q, r = divmod(n, 3)
6 if r == 0:
7 return 3 ** q
8 if r == 1:
9 return 3 ** (q - 1) * 4
10 return 3 ** q * 2
复杂度：
- 时间 朴素 O(n²) / 优化 O(n) / 数学 O(1)（幂运算按 O(1) 记）
- 空间 O(n) / O(1)
8.3 不同的二叉搜索树
状态定义:
dp[i] = 由 i 个节点组成的不同二叉搜索树的个数
状态分析（先手推几项，规律自己会浮出来）：
n = 0：空树 dp[0] = 1
n = 1：单点 dp[1] = 1
n = 2：两种 dp[2] = 2
n = 3：五种 dp[3] = 5
dp[3] 是怎么来的——枚举谁当根：
根=1：左 0 个、右 2 个 → dp[0] × dp[2] = 2
根=2：左 1 个、右 1 个 → dp[1] × dp[1] = 1
根=3：左 2 个、右 0 个 → dp[2] × dp[0] = 2
合计 5
状态转移:
dp[i] += dp[j] × dp[i-j-1] j = 0 … i-1
└ 左子树 j 个 └ 右子树 i-j-1 个（-1 是根自己）
初始化：dp[0] = 1，其余 0
返回：dp[n]
代码：
1class Solution:
2 def numTrees(self, n: int) -> int:
3 dp = [0] * (n + 1)
4 dp[0] = 1
5 for i in range(1, n + 1):
6 for j in range(i): # j = 左子树节点数
7 dp[i] += dp[j] * dp[i - j - 1]
8 return dp[n]
这就是卡特兰数
1, 1, 2, 5, 14, 42, …，通项C(2n, n) / (n+1)。合法括号序列、出栈序列、凸多边形三角剖分都是同一个数列：认出"枚举分割点 + 左右相乘"这个形状，就认出了卡特兰数。
复杂度：
- 时间 O(n²)
- 空间 O(n)
9 01 背包模板
9.1 问题与分类
背包问题：有一个最大容量为 W 的背包，和若干物品，每件物品有重量 w[i] 和价值 v[i]。挑哪些物品装进去，能让总价值最大？
按每件物品可以拿几次分家：
| 类型 | 每件物品 | 一维遍历方向 |
|---|---|---|
| 01 背包 | 最多拿 1 次 | 容量倒序 |
| 完全背包 | 想拿几次拿几次 | 容量正序 |
这份笔记的核心就一句话 “每件只能拿一次"这个约束，最后落在代码里就是一个倒序循环。 后面四道题全是同一个模板换皮：难的不是 DP，是看出它是个背包——把题目里的东西翻译成"容量、重量、价值”。
9.2 二维写法
状态定义:
dp[i][j] = 从下标 [0, i] 的物品里任选，装进容量为 j 的背包，能得到的最大价值
状态转移: 第 i 件物品只有拿与不拿两种命运：
不拿：dp[i][j] = dp[i-1][j]
拿 ：dp[i][j] = dp[i-1][j - w[i]] + v[i] 需要 j >= w[i]
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
初始化（表的尺寸是 n × (W+1)，n 件物品、容量 0…W）：
第 0 行：j >= w[0] 时 dp[0][j] = v[0]，其余为 0
第 0 列：容量为 0 什么都装不下，全 0
遍历顺序：两个来源都在上一行，所以行必须从上往下；同一行内 j 正序倒序都可以（互不干扰）
代码（二维）：
1class Solution:
2 def knapsack_2d(self, n: int, nums: List[int]) -> int:
3 """
4 args:
5 n: 背包容量
6 nums: 背包的体积和价值(相等)
7 """
8 m = len(nums)
9 dp = [[0] * (n + 1) for _ in range(m)]
10
11 for j in range(nums[0], n + 1):
12 dp[0][j] = nums[0]
13
14 for i in range(1, m):
15 for j in range(n + 1):
16 if j < nums[i]:
17 dp[i][j] = dp[i - 1][j]
18 else:
19 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
20 return dp[-1][-1]
代码（加哨兵行，省掉初始化）：
1class Solution:
2 def knapsack_2d(self, n: int, nums: List[int]) -> int:
3 """
4 args:
5 n: 背包容量
6 nums: 背包的体积和价值(相等)
7 """
8 m = len(nums)
9 dp = [[0] * (n + 1) for _ in range(m + 1)]
10
11 for i in range(1, m + 1):
12 num = nums[i - 1]
13 for j in range(n + 1):
14 if j < num:
15 dp[i][j] = dp[i - 1][j]
16 else:
17 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - num] + num)
18 return dp[-1][-1]
复杂度：
- 时间 O(mn)
- 空间 O(mn)
9.3 一维滚动写法
状态定义:
dp[j] = 容量为 j 的背包能装下的最大价值（把二维表的行压掉，原地滚动）
状态转移:
j < w[i] ：dp[j] 保持不变（装不下，直接沿用上一轮）
j >= w[i]：dp[j] = max(dp[j], dp[j - w[i]] + v[i])
└ 旧值=不拿 └ 旧值=拿
初始化：全 0，不需要额外处理第一件物品
遍历顺序：外层物品正序，内层容量倒序
两层循环不能交换 必须是外层物品、内层容量。如果反过来（外层容量、内层物品），在倒序的容量下每个容量只会装进一件物品，答案会变小——那已经不是 01 背包了。 完全背包的一维写法可以交换（因为它正序、可重复拿），但 01 背包不行。这是这个模板里唯一不能动的结构。
代码（一维）：
1class Solution:
2 def knapsack_1d(self, n: int, nums: List[int]) -> int:
3 """
4 args:
5 n: 背包容量
6 nums: 背包的体积和价值(相等)
7 """
8 dp = [0] * (n + 1)
9 for num in nums:
10 for j in range(n, num - 1, -1):
11 dp[j] = max(dp[j], dp[j - num] + num)
12 return dp[-1]
复杂度：
- 时间 O(mn)
- 空间 O(n)
9.4 判定型：能否恰好装满 分割等和子集
问题转换：
把数组分成两个和相等的子集：只要找出一个子集，其和为 total / 2，剩下的自然就是另一半。所以不必真的去"分"，只需回答：能否从数组里挑出若干个数，恰好凑出 total // 2
翻译成背包：
| 背包的概念 | 本题对应 |
|---|---|
| 容量 W | total // 2 |
| 物品重量 w[i] | nums[i] |
| 物品价值 v[i] | nums[i]（同一个数既是重量也是价值） |
| 求什么 | 装到最满是多少 → 是否等于容量 |
“恰好装满"的判定技巧 直接跑最大价值背包，最后看
dp[target] == target：既然重量和价值取同一个数，那么"装进去的总价值 = 装进去的总重量”。如果最大价值恰好顶到容量，说明真的把背包塞满了。
提前判断：total 为奇数时直接 False，奇数没法均分
代码：
1class Solution:
2 def canPartition(self, nums: List[int]) -> bool:
3 total = sum(nums)
4 if total % 2:
5 return False
6 target = total // 2
7 dp = [0] * (target + 1)
8 for num in nums:
9 for j in range(target, num - 1, -1):
10 dp[j] = max(dp[j], dp[j - num] + num)
11 return dp[target] == target
复杂度：
- 时间 O(n · total)
- 空间 O(total)
9.5 最优型：尽量装满 最后一块石头的重量 II
问题转换：
每次相撞留下 |x - y|，多次相撞后的结果，等价于给每块石头配一个 ±1 的符号：
$$ans = |\sum Sign_{i} * stone_{i}|, i \in {-1, 1}$$
于是问题变成把石头分成两堆 A、B，求两堆之差的最小值：
A + B = total, |A - B| = ans
设 B 是较小的那堆 ⇒ ans = total - 2B
想让 ans 尽量小 ⇔ 让 B 尽量大，且 B <= total / 2
翻译成背包：容量 total // 2，重量 = 价值 = 石头重量，能装多满装多满。
容量取
total // 2向下取整，前提就自动成立 装出来的 B 必然<= total/2，所以"B 是较小那堆"不用额外验证，返回值total - 2 * dp[target]也一定非负，不需要再套abs
返回：total - 2 * dp[total // 2]
代码：
1class Solution:
2 def lastStoneWeightII(self, stones: List[int]) -> int:
3 total = sum(stones)
4 target = total // 2
5 dp = [0] * (target + 1)
6 for s in stones:
7 for j in range(target, s - 1, -1):
8 dp[j] = max(dp[j], dp[j - s] + s)
9 return total - 2 * dp[target]
和 416 就差最后一行 416 问"能不能刚好劈成两半"（
dp[target] == target），1049 问"劈得最接近时差多少"（total - 2*dp[target]）。同一个背包，两种读法。 416 其实就是 1049 结果为 0 的特例。
复杂度：
- 时间 O(n · total)
- 空间 O(total)
9.6 计数型：装满的方案数 目标和
问题转换：
设取 + 号的数之和为 P、取 - 号的为 N：
P - N = target
P + N = total
⇒
P = (total + target) / 2
N 被 P 唯一决定，所以只需要数：从 nums 里挑若干个数，和恰好为 P，有多少种挑法，即"装满容量 P 的背包有几种装法"。
状态转移（求方案数，用加法）:
dp[j] += dp[j - num]
初始化：dp[0] = 1
这个 1 是种子，写成 0 全表塌掉 含义是"凑出和为 0 的方案有 1 种：一个数都不选"。它是所有累加的起点，填 0 的话
dp会恒为 0。
必须先挡掉的两个边界：
(total + target) 为奇数 → P 不是整数，返回 0
abs(target) > total → 怎么配符号都够不着，返回 0
注意 target 可以是负数 第二条判断要写
abs(target) > total。只写target > total的话，target很负时P会算成负数，[0] * (p + 1)直接开出一个负长度的数组。
代码：
1class Solution:
2 def findTargetSumWays(self, nums: List[int], target: int) -> int:
3 total = sum(nums)
4 if abs(target) > total or (total + target) % 2:
5 return 0
6 p = (total + target) // 2
7 dp = [0] * (p + 1)
8 dp[0] = 1
9 for num in nums:
10 for j in range(p, num - 1, -1):
11 dp[j] += dp[j - num]
12 return dp[p]
复杂度：
- 时间 O(n · total)
- 空间 O(total)
9.7 二维费用背包 一和零
问题转换：
物品是字符串，但它占两种资源：用掉几个 0、用掉几个 1。所以背包有两个容量维度：
| 背包的概念 | 本题对应 |
|---|---|
| 容量 | 两个：最多 m 个 0、最多 n 个 1 |
| 物品重量 | 该字符串里 0 的个数、1 的个数 |
| 物品价值 | 1（每选一个字符串，答案 +1） |
| 求什么 | 最大价值 = 最多能选几个字符串 |
状态定义:
dp[i][j] = 最多用 i 个 0、j 个 1 时，能凑出的最大字符串个数。表的尺寸 (m+1) × (n+1)
这里的 i、j 是两个容量，不是"物品 × 容量" 别跟前面二维背包的
dp[物品][容量]混起来。这张表已经把物品那一维压掉了（等价于一维滚动），i、j 分别是 0 的预算和 1 的预算。 对应关系也别写反：i ↔ 0 的个数 ↔ m，j ↔ 1 的个数 ↔ n。
状态转移:
不选这个字符串：dp[i][j]
选这个字符串 ：dp[i - zeros][j - ones] + 1
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
初始化：全 0
遍历顺序：外层遍历物品（字符串），内层两个容量维度都倒序
二维费用不过是把倒序做两遍 本质仍是 01 背包的一维滚动，只是"当前状态"由一个下标变成一对下标。多一个费用维度，就多一层倒序循环，其余一模一样。
代码：
1class Solution:
2 def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4 for s in strs: # 先物品
5 zeros = s.count('0')
6 ones = len(s) - zeros
7 for i in range(m, zeros - 1, -1): # 两个容量都倒序
8 for j in range(n, ones - 1, -1):
9 dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
10 return dp[m][n]
复杂度：
- 时间 O(len(strs) · m · n)
- 空间 O(m·n)
10 完全背包
10.1 主线：和 01 背包只差一个下标
问题：有一个容量为 W 的背包和 N 件物品，第 i 件物品重量为 w[i]、价值为 v[i]，每种物品都有无穷多个，怎么拿能让背包价值最大？
和 01 背包相比，唯一的变化是"每件物品能拿几次"：
| 01 背包 | 完全背包 | |
|---|---|---|
| 每件物品 | 最多拿 1 次 | 想拿几次拿几次 |
| “拿"这一支的来源 | 上一行 dp[i-1][j-w] | 本行 dp[i][j-w] |
| 一维遍历方向 | 容量倒序 | 容量正序 |
10.2 二维写法
状态定义:
dp[i][j] = 从下标为 [0, i] 的物品里选，每种可以拿无数次，放进容量为 j 的背包，价值总和最大是多少
状态转移:
不拿：dp[i][j] = dp[i-1][j]
拿 ：dp[i][j] = dp[i][j - w[i]] + v[i] 注意是 dp[i]，不是 dp[i-1]
dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])
初始化（两种写法，和 01 背包的两种写法完全对应）：
① 不加哨兵，表尺寸 m × (W+1)：
第 0 行需要手填：j >= w[0] 时 dp[0][j] = dp[0][j - w[0]] + v[0]，其余 0
② 加哨兵行，表尺寸 (m+1) × (W+1)，全 0：
第 0 行代表"一件都不选"，天然全 0，不需要手填
遍历顺序：从上往下，从左往右（j 正序，因为"拿"这一支要读本行左边已经算出来的值）
10.3 一维滚动写法
状态定义:
dp[j] = 处理到当前物品时，容量为 j 的背包里，价值最大总和
状态转移:
不拿：dp[j]（沿用旧值）
拿 ：dp[j - w[i]] + v[i]
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
初始化：全 0
遍历顺序：外层物品从上到下，内层容量正序（从左往右）
代码（二维，加哨兵）：
1class Solution:
2 def backpackfull(self, n: int, nums: List[int]) -> int:
3 """
4 n: 容量
5 nums: 可选物品，体积和价值相等
6 """
7 m = len(nums)
8 dp = [[0] * (n + 1) for _ in range(m + 1)]
9 for i in range(1, m + 1):
10 num = nums[i - 1]
11 for j in range(n + 1):
12 dp[i][j] = dp[i - 1][j]
13 if j >= num:
14 dp[i][j] = max(dp[i][j], dp[i][j - num] + num)
15 return dp[m][n]
代码（一维）：
1class Solution:
2 def backpackfull(self, n: int, nums: List[int]) -> int:
3 dp = [0] * (n + 1)
4 for num in nums:
5 for j in range(num, n + 1): # 正序
6 dp[j] = max(dp[j], dp[j - num] + num)
7 return dp[n]
复杂度：
- 时间 O(n·W)
- 空间 二维 O(n·W) / 一维 O(W)
10.4 计数型：组合还是排列，看物品维还在不在
这一节两道题的转移几乎一样，但循环顺序刚好相反，答案也刚好不同，判据只有一句话：顺序不同的方案算不算两种。
| 循环顺序 | 物品维 | 求什么 | |
|---|---|---|---|
| 518 | 外层物品，内层容量 | 存在（被压进外层循环） | 组合数 |
| 377 | 外层容量，内层物品 | 不存在（枚举"最后一步选谁”） | 排列数 |
判断一道题要哪种，别背规则，读题 找题干里有没有"顺序不同的序列算不同方案"这句话。写着就是排列（377），没写就是组合（518）。377 的题名叫"组合总和"，但题目内容其实求的是排列——名字不可靠，题干才可靠。
10.4.1 零钱兑换 II
问题分析：物品是硬币，价值都等于面额本身，求"凑出 amount 的组合数"——顺序不同不重复计数，所以求的是组合数，遍历顺序为外层物品、内层容量。
状态定义:
dp[j] = 凑成金额 j 的方案数
状态转移:
j < coin ：dp[j] 不变
j >= coin：dp[j] += dp[j - coin]
初始化：关注定义，dp[0] = 1（凑出 0 元有 1 种方法：什么都不拿），这是整表累加的种子
遍历顺序：外层硬币（保证组合不重复），内外循环不可交换
返回：dp[amount]
代码：
1class Solution:
2 def change(self, amount: int, coins: List[int]) -> int:
3 dp = [0] * (amount + 1)
4 dp[0] = 1
5 for c in coins:
6 for j in range(c, amount + 1):
7 dp[j] += dp[j - c]
8 return dp[amount]
复杂度：
- 时间 O(len(coins)·amount)
- 空间 O(amount)
10.4.2 组合总和 Ⅳ
问题分析：题目明确"顺序不同的序列视为不同的组合"，所以此题求的其实是排列数，遍历顺序为外层容量、内层物品。
状态定义:
dp[j] = 凑成和为 j 的排列个数
状态转移:
j < num ：dp[j] 不变
j >= num：dp[j] += dp[j - num]
转移式和 518 一字不差，差别全在循环顺序
dp[j] = Σ dp[j-num]（对所有 num）本质是在枚举"最后一个数是谁"——这里根本没有物品维，j只能放外层，每个j都要把所有面额过一遍。1+2 和 2+1 因为"最后一步"不同而被分开计数。
初始化：考虑定义，dp[0] = 1（空序列的和为 0）
遍历顺序：外层容量正序，内层遍历 nums
返回：dp[target]
代码：
1class Solution:
2 def combinationSum4(self, nums: List[int], target: int) -> int:
3 dp = [0] * (target + 1)
4 dp[0] = 1
5 for j in range(1, target + 1):
6 for num in nums:
7 if j >= num:
8 dp[j] += dp[j - num]
9 return dp[target]
复杂度：
- 时间 O(target·len(nums))
- 空间 O(target)
10.5 最优型：求最少个数
这两题物品的"价值"都恒为 1（每选一次贡献 1 个计数），求的是最少选几次——完全背包求最优值。转移式的形状统一：
dp[i] = min(dp[i], dp[i - 该物品] + 1)
价值恒为 1、求最小值时，两层循环谁在外都无所谓（跟计数型不同，最优值不区分"怎么凑出来的"，只看结果）
10.5.1 零钱兑换
问题分析：视为背包，物品是硬币，价值都为 1（不是面额本身），求装满容量 amount 所需的最少物品数（不是最大价值）。
状态定义:
dp[j] = 凑出金额 j 所需的最少硬币数
状态转移:
dp[j] = min(dp[j], dp[j - c] + 1)
└不拿(旧值) └拿(用了这枚硬币)
初始化：这题求最小值，不能填 0，填 0 会让 dp[j-c]+1 从一个虚假的 0 起步。
dp[j] = INF （j >= 1）
dp[0] = 0
返回：
dp[amount] 若 dp[amount] != INF
-1 若 dp[amount] == INF
代码：
1class Solution:
2 def coinChange(self, coins: List[int], amount: int) -> int:
3 dp = [float("inf")] * (amount + 1)
4 dp[0] = 0
5 for c in coins:
6 for j in range(c, amount + 1):
7 dp[j] = min(dp[j], dp[j - c] + 1)
8 return dp[amount] if dp[amount] != float("inf") else -1
复杂度：
- 时间 O(len(coins)·amount)
- 空间 O(amount)
10.5.2 完全平方数
状态定义:
dp[i] = 凑出 i 所需的最少完全平方数个数
状态转移:
dp[i] = min(dp[i], dp[i - j*j] + 1) j*j <= i
初始化：求最小值，只能填 INF：
dp[i] = INF （i >= 1）
dp[0] = 0
代码：
1class Solution:
2 def numSquares(self, n: int) -> int:
3 dp = [float("inf")] * (n + 1)
4 dp[0] = 0
5 for i in range(1, n + 1):
6 j = 1
7 while j * j <= i:
8 dp[i] = min(dp[i], dp[i - j * j] + 1)
9 j += 1
10 return dp[n]
复杂度：
- 时间 O(n√n)
- 空间 O(n)
BFS：把"凑出 n"看成图上的最短路——从 n 出发，每步减去一个完全平方数，最少几步到 0。
1from collections import deque
2
3class Solution:
4 def numSquares(self, n: int) -> int:
5 squares = []
6 k = 1
7 while k * k <= n:
8 squares.append(k * k)
9 k += 1
10 visited = {0, n}
11 q = deque([n])
12 steps = 0
13 while q:
14 steps += 1
15 for _ in range(len(q)):
16 cur = q.popleft()
17 for s in squares:
18 nxt = cur - s
19 if nxt == 0:
20 return steps
21 if nxt > 0 and nxt not in visited:
22 visited.add(nxt)
23 q.append(nxt)
24 return -1
BFS 为什么常常更快 DP 老老实实填满
dp[1..n]每一格；BFS 一旦触达 0 立刻返回。这题答案通常很小（下面数学解法会说明最多 4），大多数状态根本不需要探索。实测n=12345时 BFS 比 DP 快一个数量级以上。
数论公式（拉格朗日四平方和定理 + 勒让德三平方和定理）：答案只有 1/2/3/4 四种可能，可以 O(√n) 直接判定。
1import math
2
3class Solution:
4 def numSquares(self, n: int) -> int:
5 def is_square(x: int) -> bool:
6 r = math.isqrt(x)
7 return r * r == x
8
9 if is_square(n):
10 return 1
11 t = n
12 while t % 4 == 0:
13 t //= 4
14 if t % 8 == 7:
15 return 4
16 for a in range(math.isqrt(n) + 1):
17 if is_square(n - a * a):
18 return 2
19 return 3
10.6 判定型：物品不是数字 单词拆分
问题分析：给定字符串 s 和词典 wordDict，判断 s 能否被切分成词典单词的拼接（单词可重复使用）。这题的"物品"是字符串而不是数字，重量、价值这些数值概念不再适用，但"容量正序、每种物品可重复取"的骨架不变——本质仍是完全背包，只是"装满"变成了字符串完全匹配。
状态定义:
dp[i] = 前缀 s[0:i] 能否被词典单词拼出
状态转移：枚举最后一个单词的起点 j
dp[i] = True，若存在 j < i 使得 dp[j] = True 且 s[j:i] ∈ words
初始化：
dp[i] 全部为 False （i ∈ [0, n]，先全填 False）
dp[0] = True （空前缀天然可切）
剪枝：j 只需要枚举 [max(0, i - maxlen), i)，maxlen 是词典里最长单词的长度
为什么可以跳过更早的 j 若
j < i - maxlen，s[j:i]的长度已经超过词典最长单词，不可能出现在words里，连查都不用查。内层枚举范围从O(i)收窄到O(maxlen)。
返回：dp[n]
代码：
1class Solution:
2 def wordBreak(self, s: str, wordDict: List[str]) -> bool:
3 words = set(wordDict)
4 maxlen = max(len(w) for w in words)
5 n = len(s)
6 dp = [False] * (n + 1)
7 dp[0] = True
8 for i in range(1, n + 1):
9 for j in range(max(0, i - maxlen), i):
10 if dp[j] and s[j:i] in words:
11 dp[i] = True
12 return dp[n]
复杂度：
- 不剪枝是
O(n²)次子串匹配 maxlen剪枝后是O(n·maxlen)，词典单词都短时效果明显