INTERVIEW PREPARATION / DYNAMIC PROGRAMMING
动态规划 13 道 LeetCode 题，串起递推基础、一维最优、网格模型、划分与子序列、双序列 DP 。每题包含完整 Python 3 答案、关键语句解释、手算推演、复杂度与易错点。
13 道题 5 个阶段 30 份完整代码 离线复习 · 进度保存
先用一句完整的话定义 dp，再写公式。 每次看到 dp[i]，都应能回答：它考虑了哪些元素？是否必须选择最后一个？保存数量、可行性还是最优值？
学习路线 · 先建模，再优化 阶段 题目（建议顺序） 过关标准 01 · 基础知识 · 从递归到递推 509 斐波那契数 → 70 爬楼梯 → 118 杨辉三角 从重复计算出发，学会给状态命名、设置边界并按依赖顺序填表。 02 · 核心模板 · 一维最优决策 198 打家劫舍 → 53 最大子数组和 → 152 乘积最大子数组 区分前缀最优与结尾最优，理解取 max、维护全局答案与保留双极值的原因。 03 · 典型应用 · 网格动态规划 62 不同路径 → 63 不同路径 II → 64 最小路径和 同一张依赖图，可以累计路径数、处理障碍，也可以选择最小代价。 04 · 状态扩展 · 划分与子序列 139 单词拆分 → 300 最长递增子序列 从固定前驱走向枚举前驱，并学习用贪心不变量和二分改造状态。 05 · 进阶算法 · 双序列动态规划 1143 最长公共子序列 → 72 编辑距离 使用两个前缀长度定义二维状态，比较匹配、跳过与编辑三种转移，再压缩空间。
先理解 DP：把重复的子问题只算一次 动态规划适合能够拆为相互依赖的较小状态的问题。重叠子问题 意味着多条推导路径会遇到相同状态；求最优解时还要有最优子结构 ：当前最优值能由适当子问题的最优值构成。状态必须包含影响后续选择所需的信息；乘积题保留最大值还不够，还需要最小值。
把状态看作节点、把依赖看作箭头，就得到一张无环有向图。记忆化按需访问节点，递推则按拓扑顺序填表；两者都是 DP。不要为了“套 DP”给状态附加没有作用的维度。
F(i−2) F(i−1) F(i) 先确定依赖，再决定遍历顺序 滚动更新：a, b = b, a + b 箭头表示旧状态对新状态的依赖；这张图是一个无环有向图。 五步法 必须说清楚的问题 本手册中的例子 1 · 定义状态 下标表示位置还是前缀长度？是否必须以它结尾？ 53 必须结尾；198 只考虑前 i 间 2 · 找转移 按最后一步或最后一次选择分类，如何覆盖全部情况？ 70 两种步长相加；198 偷或不偷取 max 3 · 设边界 最小合法状态是什么？不可达应设为什么？ 139 空前缀 True；64 越界为 +∞ 4 · 定顺序 转移读取的状态是否已经算出？ 网格按行从左到右；杨辉单行更新从右到左 5 · 定答案与优化 最终答案在哪？能否丢弃不再使用的旧状态？ 300 取 max(dp)；1143 保存一行与旧对角线
计数、可行性、最优化，聚合方式不同。 计数常用加法，存在性常用 OR，最大值用 max，最小值用 min。初始化与状态含义一起确定，不能仅凭习惯把整张表设为 0。
问题类型 常见初值 本专题例子 路径计数 不可达为 0；起点空方案为 1 70、62、63 判断可行 不可行为 False；空前缀 True 139 求非空最大值 以首个合法元素初始化 53、152 求最小代价 不可达为 +∞；合法起点写真实代价 64 两个前缀的比较 显式增设空前缀行列 1143 为 0；72 为长度
复杂度与空间压缩：不要只数循环层数 时间通常是“状态数 × 每个状态枚举的候选数 × 单次操作成本”。Python 的字符串切片会复制字符，不能忽略；哈希表查找的期望常数时间也不等于新字符串哈希免费。空间要区分辅助状态、递归栈和必须返回的输出；杨辉三角的全部输出本来就占 O(r²)。除特别说明外，整数运算按常数时间估算，适用于本题规模。
滚动数组优化的是存储，不改变状态定义。写一维版本之前，先在二维依赖图上标明哪些值来自旧行、哪些来自新行。只求数值时可压缩；需要重建具体方案时通常要保留更多信息。
OFFLINE DP LAB
亲手改一个障碍，看状态如何传播 3×3 网格，左上出发、右下结束，只能向右或下。点击任意格子切换障碍，包括起点与终点。数字表示到达该格的路径数；键盘 Tab 与 Enter 也可操作。
恢复中心障碍 计算规则：先检查障碍并归零；可走的起点赋 1；其他格子累加上方与左方。中心有障碍时答案为 2，清空障碍后为 6。
STAGE 01 基础知识 · 从递归到递推从重复计算出发，学会给状态命名、设置边界并按依赖顺序填表。
01 LeetCode 509 斐波那契数难度：简单 ｜ 核心：重叠子问题 / 记忆化 / 滚动变量
题意与输入边界 输入整数 n（0 ≤ n ≤ 30），返回第 n 个斐波那契数；第 0 项为 0，第 1 项为 1。
解题思路 · 状态、转移与正确性 状态定义： dp[i] 表示 F(i)，即第 i 项的数值；它不是“方案数”的通用模板。
F(0)=0, F(1)=1；F(i)=F(i−1)+F(i−2)
直接递归会反复求 F(3)、F(2) 等同一子问题。记忆化保证每个状态只求一次；表格按下标递增计算，转移时两个前驱已知。只依赖前两项，因此还能压缩成两个变量。
解法一 · 记忆化搜索 按定义递归，使用缓存保存每个 k 的结果；这是从问题向下拆解的自顶向下 DP。
from functools import lru_cache
class Solution:
def fib (self, n: int ) -> int :
@lru_cache (None )
def dfs (k):
if k < 2 :
return k
return dfs (k - 1 ) + dfs (k - 2 )
return dfs (n)
关键代码解释 缓存的键是 k，不要让不同状态共用一个结果。 递归函数定义在方法内部，每次调用获得独立缓存；n=0、1 直接触发边界。 时间复杂度： O(n)：n+1 个状态，每个状态一次加法。
空间复杂度： O(n)：缓存与最深 O(n) 递归栈。
解法二 · 数组递推 显式存下从 F(0) 到 F(n) 的所有状态，便于观察和调试。
class Solution:
def fib (self, n: int ) -> int :
if n < 2 :
return n
dp = [0 ] * (n + 1 )
dp[1 ] = 1
for i in range (2 , n + 1 ):
dp[i] = dp[i - 1 ] + dp[i - 2 ]
return dp[n]
关键代码解释 先返回 n<2，避免长度为 1 时访问 dp[1]。 range 的右边界必须是 n+1，才能计算第 n 项。 时间复杂度： O(n)。
空间复杂度： O(n)：状态数组。
解法三 · 滚动变量（推荐提交） 每轮开始 a=F(i−2)、b=F(i−1)，计算后整体向前移动。
class Solution:
def fib (self, n: int ) -> int :
if n < 2 :
return n
a, b = 0 , 1
for i in range (2 , n + 1 ):
a, b = b, a + b
return b
关键代码解释 Python 同时赋值先计算右侧两个旧值，再更新左侧。 若先写 a=b，再写 b=a+b，就丢失了旧 a。 时间复杂度： O(n)。
空间复杂度： O(1)：两个滚动变量。
示例推演 · 手算状态 n=5 → 5；边界 n=0 → 0，n=1 → 1。
i F(i−2) F(i−1) F(i) 2 0 1 1 3 1 1 2 4 1 2 3 5 2 3 5
解法比较与面试表达 记忆化最接近数学定义，但有栈开销；数组适合展示全部状态；滚动变量最省空间。这里按面试常用的算术操作计数分析，题目范围内整数大小有限。
易错点与边界复查 无缓存递归时间指数增长，不是 O(n)。 不要把 F(0) 写成 1；它与爬楼梯中的空方案含义不同。 02 LeetCode 70 爬楼梯难度：简单 ｜ 核心：计数 DP / 最后一步分类 / 空方案
题意与输入边界 输入 n 阶楼梯（1 ≤ n ≤ 45）。每次上 1 或 2 阶，求恰好到楼顶的不同走法数；先 1 后 2 与先 2 后 1 是不同走法。
解题思路 · 状态、转移与正确性 状态定义： dp[i] 表示恰好到达第 i 阶的方法数。dp[0]=1 代表从地面出发、不走任何一步的唯一空方案。
dp[0]=1, dp[1]=1；dp[i]=dp[i−1]+dp[i−2]
按最后一步分成“从 i−1 走 1 阶”和“从 i−2 走 2 阶”。两类互斥，覆盖所有路径，所以相加。不要枚举所有完整走法，数量会快速增长。
解法一 · 计数数组 从地面初始化，依次求每一阶的方案数。
class Solution:
def climbStairs (self, n: int ) -> int :
dp = [0 ] * (n + 1 )
dp[0 ] = 1
for i in range (1 , n + 1 ):
dp[i] = dp[i - 1 ]
if i >= 2 :
dp[i] += dp[i - 2 ]
return dp[n]
关键代码解释 i=1 时只有来自第 0 阶的一种走法，不能读取 dp[-1]。 把“求个数”写成求 max，会漏掉另一类路径。 解法二 · 滚动计数（推荐） 从 dp[0]=dp[1]=1 出发保留两项，递推到 n。
class Solution:
def climbStairs (self, n: int ) -> int :
a, b = 1 , 1
for i in range (2 , n + 1 ):
a, b = b, a + b
return b
关键代码解释 n=1 时循环为空，直接返回 1。 a、b 对应前两阶的方案数，而不是当前台阶高度。 示例推演 · 手算状态 n=4 → 5：1111、112、121、211、22；n=1 → 1，n=2 → 2。
阶数 来自前一阶 来自前两阶 总走法 0 — — 1 1 1 0 1 2 1 1 2 3 2 1 3 4 3 2 5
解法比较与面试表达 先写数组解释计数来源，再压缩空间。两种方法结果一致；扩展为允许步长集合时，应对每个合法前驱累加，不能盲用两变量。
易错点与边界复查 爬楼梯的答案等于 F(n+1)，不是 F(n)。 顺序不同算不同方法；这不是忽略排列顺序的硬币组合题。 03 LeetCode 118 杨辉三角难度：简单 ｜ 核心：二维递推 / 行边界 / 输出空间
题意与输入边界 返回杨辉三角前 numRows 行（1 ≤ numRows ≤ 30）。每行首尾为 1，中间位置等于上一行相邻两个数之和。
解题思路 · 状态、转移与正确性 状态定义： 第 i 行使用 0 起始下标，长度为 i+1；row[j] 表示该行第 j 个数。
P[i][0]=P[i][i]=1；P[i][j]=P[i−1][j−1]+P[i−1][j]
一行完全由上一行确定。两侧边界没有两个父项，直接设为 1。递推按行进行，即保证上一行先完成。整个三角形必须返回，因此输出本身就有 Θ(r²) 个元素。
解法一 · 逐行新建（推荐） 每行先填 1，只计算内部位置；结果列表兼作历史状态表。
from typing import List
class Solution:
def generate (self, numRows: int ) -> List [List [int ]]:
ans = []
for i in range (numRows):
row = [1 ] * (i + 1 )
for j in range (1 , i):
row[j] = ans[i - 1 ][j - 1 ] + ans[i - 1 ][j]
ans.append (row)
return ans
关键代码解释 range(1,i) 自动跳过两端；前两行没有内部项。 每一轮创建新的 row，避免所有行引用同一列表。 时间复杂度： O(r²)，r=numRows；输出元素数决定下界。
空间复杂度： 总空间 O(r²) 含输出；除结果及当前行外为 O(1)。当前行最终进入输出。
解法二 · 单行从右向左更新 保留一行，在末尾补 1，再从右往左更新中间项；每次把快照加入答案。
from typing import List
class Solution:
def generate (self, numRows: int ) -> List [List [int ]]:
ans, row = [], []
for i in range (numRows):
row.append (1 )
for j in range (i - 1 , 0 , -1 ):
row[j] += row[j - 1 ]
ans.append (row[:])
return ans
关键代码解释 逆序保证 row[j−1] 仍是上一行的值。 row[:] 生成快照；直接 ans.append(row) 会使所有行随同一个列表改变。 时间复杂度： O(r²)：更新及逐行复制。
空间复杂度： 辅助 O(r)，输出 O(r²)；返回完整三角形不能宣称总空间 O(r)。
示例推演 · 手算状态 numRows=5 → [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]；numRows=1 → [[1]]。
行下标 i 边界 内部推导 该行 0 1 无 [1] 1 1,1 无 [1,1] 2 1,…,1 1+1=2 [1,2,1] 3 1,…,1 1+2=3；2+1=3 [1,3,3,1] 4 1,…,1 1+3=4；3+3=6 [1,4,6,4,1]
解法比较与面试表达 逐行新建更清楚且自然返回所有行；单行方法用于理解逆序更新，但本题仍须保存完整输出，没有降低输出空间。
易错点与边界复查 不要使用 [[1]*r]*r 创建多行，它们共享引用。 一维更新若从左往右，当前行新值会污染还需要的旧值。 阶段验收： 从重复计算出发，学会给状态命名、设置边界并按依赖顺序填表。 隐去代码，独立写出本阶段各题的状态、初值、递推式，再用一个最小输入和一个反例验证。
STAGE 02 核心模板 · 一维最优决策区分前缀最优与结尾最优，理解取 max、维护全局答案与保留双极值的原因。
04 LeetCode 198 打家劫舍难度：中等 ｜ 核心：前缀最优 / 选或不选 / 间隔约束
题意与输入边界 给出一排房屋的非负金额 nums，不能同时选择相邻房屋，求可获得的最大金额。至少有一间房，允许不偷。
解题思路 · 状态、转移与正确性 状态定义： dp[i] 表示只考虑前 i 间房的最大收益，当前房屋金额为 nums[i−1]。它不要求必须偷第 i 间。
dp[0]=0；dp[1]=nums[0]；dp[i]=max(dp[i−1], dp[i−2]+nums[i−1])
最优方案只有两种：不偷当前房屋，收益来自前 i−1 间；偷当前房屋，前一间不能偷，收益来自前 i−2 间。两类取最大即得到最优解。仅比较奇数位与偶数位金额不够，例如 [2,1,1,2] 可以偷首尾，收益为 4。
解法一 · 前缀数组 以“前多少间”为下标，空前缀收益为 0。
from typing import List
class Solution:
def rob (self, nums: List [int ]) -> int :
n = len (nums)
dp = [0 ] * (n + 1 )
dp[1 ] = nums[0 ]
for i in range (2 , n + 1 ):
dp[i] = max (dp[i - 1 ], dp[i - 2 ] + nums[i - 1 ])
return dp[n]
关键代码解释 dp 下标是数量，nums 下标是位置，两者相差 1。 dp[i−1] 可以继承，不应强制包含当前房屋。 解法二 · 滚动状态（推荐） 每处理一个金额 x，用前两轮的最优收益决定新收益。
from typing import List
class Solution:
def rob (self, nums: List [int ]) -> int :
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max (prev1, prev2 + x)
return prev1
关键代码解释 循环前两个 0 分别表示尚未选择房屋时的基准收益。 同时赋值确保 prev2+x 使用旧 prev2。 示例推演 · 手算状态 nums=[2,7,9,3,1] → 12，选择 2、9、1；[0] → 0；[2,1,1,2] → 4。
前 i 间 当前金额 不偷 / 偷 dp[i] 0 — — 0 1 2 0 / 2 2 2 7 2 / 7 7 3 9 7 / 2+9 11 4 3 11 / 7+3 11 5 1 11 / 11+1 12
解法比较与面试表达 数组可用于回溯选择方案；滚动变量适合只返回最大收益。回溯时比较 dp[i−1] 与 dp[i−2]+nums[i−1]，相等时可能有多种最优方案。
易错点与边界复查 相邻房屋有约束，不能简单累加所有正数。 本题是一排房屋；首尾并不相邻，不要误用环形版本边界。 05 LeetCode 53 最大子数组和难度：中等 ｜ 核心：以当前位置结尾 / Kadane / 分治合并
题意与输入边界 输入非空整数数组，返回非空连续子数组的最大和。元素可以为负数，子数组必须连续。
解题思路 · 状态、转移与正确性 状态定义： end[i] 表示必须以 nums[i] 结尾的最大子数组和；全局答案为所有 end[i] 的最大值。
end[0]=nums[0]；end[i]=max(nums[i], end[i−1]+nums[i])；ans=max(end)
以 i 结尾的连续子数组要么只含 nums[i]，要么把以 i−1 结尾的子数组接上 nums[i]，没有第三种情况。旧和为负时重新开始更好；但答案不能从 0 初始化，因为空子数组不合法。
解法一 · 显式 DP 数组 写清每个下标的结尾最优，再从所有状态中取最大。
from typing import List
class Solution:
def maxSubArray (self, nums: List [int ]) -> int :
dp = [0 ] * len (nums)
dp[0 ] = nums[0 ]
for i in range (1 , len (nums)):
dp[i] = max (nums[i], dp[i - 1 ] + nums[i])
return max (dp)
关键代码解释 dp[-1] 只代表最后一个位置结尾，不能直接作为全局答案。 非空保证 nums[0] 存在；单元素数组直接返回该元素。 解法二 · Kadane 滚动变量（推荐） 用 end 保存当前结尾最优，用 ans 累积全局最优。
from typing import List
class Solution:
def maxSubArray (self, nums: List [int ]) -> int :
end = ans = nums[0 ]
for i in range (1 , len (nums)):
end = max (nums[i], end + nums[i])
ans = max (ans, end)
return ans
关键代码解释 先更新 end，再用本轮 end 更新 ans。 以 nums[0] 初始化两个变量，能正确处理全负数组。 解法三 · 四元组分治（进阶） 每个区间返回总和、最大前缀和、最大后缀和、最大子数组和。左右各自递归后 O(1) 合并。
from typing import List
class Solution:
def maxSubArray (self, nums: List [int ]) -> int :
def solve (l, r):
if l == r:
x = nums[l]
return x, x, x, x
mid = (l + r) // 2
lt, lp, ls, lb = solve (l, mid)
rt, rp, rs, rb = solve (mid + 1 , r)
total = lt + rt
prefix = max (lp, lt + rp)
suffix = max (rs, rt + ls)
best = max (lb, rb, ls + rp)
return total, prefix, suffix, best
return solve (0 , len (nums) - 1 )[3 ]
关键代码解释 跨越中点的最佳子数组必为左区间后缀 + 右区间前缀。 每层不用重新扫描区间，也不用切片，所以 T(n)=2T(n/2)+O(1)=O(n)。 时间复杂度： O(n)：每个递归节点只做常数次合并。
空间复杂度： O(log n)：平衡递归栈。
示例推演 · 手算状态 [-2,1,-3,4,-1,2,1,-5,4] → 6，对应 [4,-1,2,1]；[-5,-2,-7] → −2。
i / 值 以此结尾 end 全局 ans 决定 0 −2 −2 初始化 1 1 1 从 1 重启 2 −2 1 1−3 3 4 4 从 4 重启 4 3 4 4−1 5 5 5 接上 2 6 6 6 接上 1 7 1 6 接上 −5 8 5 6 接上 4
解法比较与面试表达 数组版最便于看状态；Kadane 最简洁；四元组法展示“保留足够信息才能合并”，也可迁移到线段树。若要返回区间，还需记录重启位置和全局左右边界。
易错点与边界复查 不能跳过中间负数拼接两个不相邻片段。 ans=0 会把全负数组错误地变成 0。 分治若每次线性扫描跨界区间，复杂度为 O(n log n)；这里的四元组版本为 O(n)。 06 LeetCode 152 乘积最大子数组难度：中等 ｜ 核心：双状态 / 负负得正 / 旧值保护
题意与输入边界 输入非空整数数组，返回非空连续子数组的最大乘积。数值可为负数或 0；题目保证任意子数组乘积在 32 位整数范围内。
解题思路 · 状态、转移与正确性 状态定义： hi[i]、lo[i] 分别表示以 i 结尾的最大与最小乘积。负数乘法会交换大小，所以两端极值都必须保存。
hi=max(x, old_hi·x, old_lo·x)；lo=min(x, old_hi·x, old_lo·x)
把 x 接在一个旧子数组后面时：x 为正数保持大小顺序，x 为负数反转顺序，x=0 则两个乘积都为 0。加上“只选择 x”，三类候选覆盖所有结尾子数组。
解法一 · 最大最小数组 分别保存每个位置的两种极值，最后在 hi 中找答案。
from typing import List
class Solution:
def maxProduct (self, nums: List [int ]) -> int :
n = len (nums)
hi, lo = [0 ] * n, [0 ] * n
hi[0 ] = lo[0 ] = nums[0 ]
for i in range (1 , n):
x = nums[i]
hi[i] = max (x, hi[i - 1 ] * x, lo[i - 1 ] * x)
lo[i] = min (x, hi[i - 1 ] * x, lo[i - 1 ] * x)
return max (hi)
关键代码解释 lo 可能是很小的负数，遇到下一次负数时变成最大正数。 只读前一项，因此更新 hi[i] 不会破坏 lo[i] 的计算。 解法二 · 两个滚动极值（推荐） 显式存下旧 hi、lo，再同时推导本轮两个极值。
from typing import List
class Solution:
def maxProduct (self, nums: List [int ]) -> int :
hi = lo = ans = nums[0 ]
for i in range (1 , len (nums)):
x = nums[i]
old_hi, old_lo = hi, lo
hi = max (x, old_hi * x, old_lo * x)
lo = min (x, old_hi * x, old_lo * x)
ans = max (ans, hi)
return ans
关键代码解释 old_hi、old_lo 同属上一轮；不能用更新后的 hi 求 lo。 候选 x 让新片段可从当前位置开始，0 之后也能正常重启。 示例推演 · 手算状态 [-2,3,-4,0,-1] → 24；[2,3,-2,4] → 6；[-2,0,-1] → 0；[-2] → −2。
x 候选：x / old_hi×x / old_lo×x 新 hi / lo ans -2 初始化 −2 / −2 -2 3 3 / −6 / −6 3 / −6 3 -4 −4 / −12 / 24 24 / −12 24 0 0 / 0 / 0 0 / 0 24 -1 −1 / 0 / 0 0 / −1 24
解法比较与面试表达 两种解法使用相同转移。数组版便于推演；滚动版减少空间。也可在 x<0 时交换 hi、lo 后计算，但显式旧值版本更便于避免更新顺序错误。
易错点与边界复查 不能套用最大和的单一状态；[-2,3,-4] 正说明最小负积有用。 最大乘积可能出现在中途，必须保存全局 ans。 把初值设为 1 会允许空子数组，单个负数时错误。 阶段验收： 区分前缀最优与结尾最优，理解取 max、维护全局答案与保留双极值的原因。 隐去代码，独立写出本阶段各题的状态、初值、递推式，再用一个最小输入和一个反例验证。
STAGE 03 典型应用 · 网格动态规划同一张依赖图，可以累计路径数、处理障碍，也可以选择最小代价。
07 LeetCode 62 不同路径难度：中等 ｜ 核心：网格计数 / 上与左 / 滚动行
题意与输入边界 m 行 n 列网格，从左上角走到右下角，每次只向右或向下移动一步，求路径总数。m、n 均为正整数。
解题思路 · 状态、转移与正确性 状态定义： dp[i][j] 表示从起点到格子 (i,j) 的路径数，包含到达当前格子的完整路径。
dp[0][j]=dp[i][0]=1；dp[i][j]=dp[i−1][j]+dp[i][j−1]
最后一步只能来自上方或左方，两类路径互斥，因此相加。首行只能一直向右，首列只能一直向下，均只有 1 条路径。按行从左到右计算可保证依赖已就绪。
解法一 · 二维表 整张表先填 1，再求内部格子。
class Solution:
def uniquePaths (self, m: int , n: int ) -> int :
dp = [[1 ] * n for _ in range (m)]
for i in range (1 , m):
for j in range (1 , n):
dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ]
return dp[m - 1 ][n - 1 ]
关键代码解释 列表推导式为每一行创建独立对象。 只有一行或一列时内部循环为空，答案保留为 1。 解法二 · 一维滚动行（推荐） 更新 dp[j] 之前它是上一行的路径数；dp[j−1] 已是当前行左边的路径数。
class Solution:
def uniquePaths (self, m: int , n: int ) -> int :
dp = [1 ] * n
for i in range (1 , m):
for j in range (1 , n):
dp[j] += dp[j - 1 ]
return dp[-1 ]
关键代码解释 左到右更新正是为了让左邻居使用本行新值。 若利用网格对称性让 n 为较小维度，可压缩至 O(min(m,n))；此代码原样为 O(n)。 时间复杂度： O(mn)。
空间复杂度： O(n)：一行。
解法三 · 组合计数（进阶对照） 每条路径固定包含 m−1 次向下、n−1 次向右。只要选择向下动作在总步数中的位置，就唯一确定一条路径，答案是组合数。下面逐项精确计算，不使用浮点数。
class Solution:
def uniquePaths (self, m: int , n: int ) -> int :
total = m + n - 2
k = min (m - 1 , n - 1 )
ans = 1
for i in range (1 , k + 1 ):
ans = ans * (total - k + i) // i
return ans
关键代码解释 第 i 轮结束，ans=C(total−k+i,i)，乘除递推保持整数。 必须先乘后整除；提前除可能截断。k=0 表示只有一行或一列，空循环返回 1。 时间复杂度： O(k) 次整数乘除，k=min(m−1,n−1)；按算术操作模型计数。
空间复杂度： O(1) 个变量；若计入大整数位数，则需要 O(log C(total,k)) 位存储，运算成本也随位数增长。
示例推演 · 手算状态 m=3,n=3 → 6；m=3,n=7 → 28；m=1,n=5 → 1；m=1,n=1 → 1。
处理的行 第 0 列 第 1 列 第 2 列 第 0 行 1 1 1 第 1 行 1 1+1=2 1+2=3 第 2 行 1 2+1=3 3+3=6
解法比较与面试表达 二维表最直观，一维版只保留必需的历史；组合计数利用固定步数通常更快。带障碍或带权网格破坏了任意步序都合法的条件，应回到 63、64 的 DP。
易错点与边界复查 二维数组不要写成 [[1]*n]*m。 一维版从右向左更新会让左方仍来自上一行，含义不符。 08 LeetCode 63 不同路径 II难度：中等 ｜ 核心：障碍归零 / 边界传播 / 可达性
题意与输入边界 给出障碍网格 obstacleGrid，0 可走、1 为障碍。从左上到右下只向右或下，求不穿过障碍的路径数。起点或终点也可能被堵住。
解题思路 · 状态、转移与正确性 状态定义： dp[i][j] 仍表示到达当前格子的路径数。任何障碍格子的状态都必须为 0。
有障碍：dp[i][j]=0；否则为上方+左方；起点可走时 dp[0][0]=1
与 62 的转移一致，但边界不再整行整列恒为 1。首行遇到障碍后，后续格子都无法从左边抵达；通用转移会自然传播这个 0。必须先判断障碍，再处理起点。
解法一 · 二维表与统一边界 越界方向视为没有路径；起点单独设为 1。
from typing import List
class Solution:
def uniquePathsWithObstacles (self, obstacleGrid: List [List [int ]]) -> int :
m, n = len (obstacleGrid), len (obstacleGrid[0 ])
dp = [[0 ] * n for _ in range (m)]
for i in range (m):
for j in range (n):
if obstacleGrid[i][j] == 1 :
continue
if i == 0 and j == 0 :
dp[i][j] = 1
else :
up = dp[i - 1 ][j] if i > 0 else 0
left = dp[i][j - 1 ] if j > 0 else 0
dp[i][j] = up + left
return dp[-1 ][-1 ]
关键代码解释 continue 保留障碍格的初值 0，也会让障碍起点保持 0。 不能直接套用无障碍题的首行全 1 初始化。 解法二 · 一维行内归零（推荐） 初始 dp[0]=1 代表起点的种子。扫描到障碍时，把从上方继承的旧路径数清除。
from typing import List
class Solution:
def uniquePathsWithObstacles (self, obstacleGrid: List [List [int ]]) -> int :
n = len (obstacleGrid[0 ])
dp = [0 ] * n
dp[0 ] = 1
for row in obstacleGrid:
for j in range (n):
if row[j] == 1 :
dp[j] = 0
elif j > 0 :
dp[j] += dp[j - 1 ]
return dp[-1 ]
关键代码解释 j=0 时不加 dp[-1]；首列路径数直接继承上一行，遇障碍则清零。 起点有障碍时第一次扫描就会令 dp[0]=0。 示例推演 · 手算状态 [[0,0,0],[0,1,0],[0,0,0]] → 2；[[1]] → 0；[[0]] → 1；[[0,1,0]] → 0。
行 障碍布局 滚动数组更新后 解释 0 0 0 0 [1,1,1] 首行只有向右 1 0 1 0 [1,0,1] 中心归零，右侧从上继承 2 0 0 0 [1,1,2] 终点由上方 1 + 左方 1
解法比较与面试表达 二维版便于对照障碍和状态；一维版空间更低。该题可视为 DAG 上的路径计数：被禁用的节点没有路径贡献。
易错点与边界复查 障碍不能只是跳过更新一维状态，否则上一行的旧值仍留在 dp[j]。 不要假设起终点一定可走。 障碍之后的首行格子可能不可达，不要无条件赋 1。 09 LeetCode 64 最小路径和难度：中等 ｜ 核心：网格最优 / 不可达设无穷 / 起点代价
题意与输入边界 非负整数网格中，从左上到右下，每次只能向右或向下，求路径上所有格子（含起点终点）的最小总和。
解题思路 · 状态、转移与正确性 状态定义： dp[i][j] 表示到达 (i,j) 的最小累计和。与路径计数不同，这里从两个前驱选择代价较小者。
dp[0][0]=grid[0][0]；dp[i][j]=min(上方,左方)+grid[i][j]
任意最优路径最后一步来自上或左。若它在该前驱之前并非最优，就可以替换为更便宜的前缀，得到更优整条路径，产生矛盾。这就是最优子结构。越界方向不存在，应视为 +∞，不能视为 0。
解法一 · 二维最短代价表 显式初始化起点，然后统一处理其余格子。
from typing import List
class Solution:
def minPathSum (self, grid: List [List [int ]]) -> int :
m, n = len (grid), len (grid[0 ])
dp = [[float ("inf" )] * n for _ in range (m)]
dp[0 ][0 ] = grid[0 ][0 ]
for i in range (m):
for j in range (n):
if i == 0 and j == 0 :
continue
up = dp[i - 1 ][j] if i > 0 else float ("inf" )
left = dp[i][j - 1 ] if j > 0 else float ("inf" )
dp[i][j] = min (up, left) + grid[i][j]
return dp[-1 ][-1 ]
关键代码解释 起点只计入一次；其余格子把本格代价加在前驱最优值之后。 此实现不修改原 grid；保存整表便于回溯路径。 解法二 · 一维滚动最小值（推荐） 用 dp[0]=0 为起点提供一个虚拟前驱；第一次处理后它就变成首格代价。
from typing import List
class Solution:
def minPathSum (self, grid: List [List [int ]]) -> int :
n = len (grid[0 ])
dp = [float ("inf" )] * n
dp[0 ] = 0
for row in grid:
for j, x in enumerate (row):
left = dp[j - 1 ] if j > 0 else float ("inf" )
dp[j] = min (dp[j], left) + x
return dp[-1 ]
关键代码解释 旧 dp[j] 是上方，新 dp[j−1] 是左方。 首列只能从上方来；虚拟种子仅在初始时为 0，不会每行重置。 示例推演 · 手算状态 [[1,3,1],[1,5,1],[4,2,1]] → 7，路径值 1→3→1→1→1；[[0]] → 0；[[1,2,3]] → 6。
行 原网格 该行最小累计和 关键计算 0 [1,3,1] [1,4,5] 首行累计 1 [1,5,1] [2,7,6] 中间 min(4,2)+5=7 2 [4,2,1] [6,8,7] 终点 min(6,8)+1=7
解法比较与面试表达 二维与滚动版都不修改输入；若直接在 grid 上累加，额外空间可为 O(1)，代价是输入被改变。只返回最小和时滚动版已足够。
易错点与边界复查 不能贪心地每次选右、下中较小值，局部小不保证后续代价小。 min 型问题的不可达状态用 +∞，计数型不可达才用 0。 有的原地解会修改 grid；复制输入或明确接受修改后再使用。 阶段验收： 同一张依赖图，可以累计路径数、处理障碍，也可以选择最小代价。 隐去代码，独立写出本阶段各题的状态、初值、递推式，再用一个最小输入和一个反例验证。
STAGE 04 状态扩展 · 划分与子序列从固定前驱走向枚举前驱，并学习用贪心不变量和二分改造状态。
10 LeetCode 139 单词拆分难度：中等 ｜ 核心：前缀可行性 / 分割点 / 字符串成本
题意与输入边界 给定字符串 s 和非空单词字典 wordDict，判断能否用字典词完整拼出 s。词可重复使用，可以不使用部分词；不能重排 s 中字符。
解题思路 · 状态、转移与正确性 状态定义： dp[i] 表示长度为 i 的前缀 s[:i] 能否被合法拆分；dp[0]=True 是连接首个单词所需的空前缀。
dp[i]=OR(dp[j] AND s[j:i]∈words)，0≤j<i
枚举最后一个单词的起点 j。前 j 个字符可拆且最后一段属于字典，就得到一个合法拆分；反过来任何合法方案也必存在这样的最后分割点。只需要一个可行方案，命中后可提前停止。
解法一 · 枚举全部分割点 字典转 set 以便查找；短路逻辑只在 dp[j] 为真时创建候选切片。
from typing import List
class Solution:
def wordBreak (self, s: str , wordDict: List [str ]) -> bool :
words = set (wordDict)
n = len (s)
dp = [False ] * (n + 1 )
dp[0 ] = True
for i in range (1 , n + 1 ):
for j in range (i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]
关键代码解释 dp[j] 是前缀长度 j，最后一段是左闭右开 s[j:i]。 set 查找期望 O(1) 不包含构造新切片与首次计算字符串哈希的 O(i−j)。 时间复杂度： Python 严格上界 O(n³+S)：O(n²) 候选，每个切片及哈希最坏 O(n)；S 为字典总字符数。
空间复杂度： O(n+S)：DP、词集合及临时候选；保守计入字典存储。
解法二 · 限制最大词长（推荐） 令 L 为最大词长。最后一个词不可能超过 L，只枚举 i−L 到 i−1 的分割点。
from typing import List
class Solution:
def wordBreak (self, s: str , wordDict: List [str ]) -> bool :
words = set (wordDict)
limit = max (map (len , wordDict), default=0 )
n = len (s)
dp = [False ] * (n + 1 )
dp[0 ] = True
for i in range (1 , n + 1 ):
for j in range (max (0 , i - limit), i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]
关键代码解释 截断范围只移除不可能是字典词的过长段，不会漏掉有效方案。 设 K=min(n,L)，每个位置至多 K 个候选、每次切片至多 K 个字符。 时间复杂度： 期望上界 O(nK²+S)，K=min(n,L)，含切片和哈希成本；抽象忽略字符串成本时为 O(nK)。
空间复杂度： O(n+S)：状态、词集合；临时切片 O(K) 不改变总上界。
解法三 · 后缀记忆化搜索 改从当前位置向右选择一个词。dfs(start) 表示后缀 s[start:] 能否完整拆分；不同拆分历史到达相同 start 时，共用缓存结果。
from functools import lru_cache
from typing import List
class Solution:
def wordBreak (self, s: str , wordDict: List [str ]) -> bool :
words = set (wordDict)
limit = max (map (len , wordDict), default=0 )
@lru_cache (None )
def dfs (start):
if start == len (s):
return True
stop = min (len (s), start + limit)
for end in range (start + 1 , stop + 1 ):
if s[start:end] in words and dfs (end):
return True
return False
return dfs (0 )
关键代码解释 缓存键是整数 start，不需要把整个剩余子串作为键反复复制。 先匹配当前词再递归。到达字符串末尾表示所有字符恰好被消费。 失败状态同样要缓存，否则大量不同路径会重复尝试同一段不可拆后缀。 时间复杂度： 期望上界 O(nK²+S)，K=min(n,L)，包含切片与哈希；可能因按需搜索而访问更少状态。
空间复杂度： O(n+S)：缓存、词集合和最深 O(n) 递归栈；本题 n≤300，迭代版更适合更长字符串。
示例推演 · 手算状态 s="leetcode", wordDict=["leet","code"] → True；"applepenapple",["apple","pen"] → True；"catsandog",["cats","dog","sand","and","cat"] → False。
i 前缀 可行分割 dp[i] 0 空串 空方案 True 1–3 l / le / lee 没有字典词结尾 False 4 leet dp[0] 且 leet 在字典 True 5–7 leetc / leetco / leetcod 均不成立 False 8 leetcode dp[4] 且 code 在字典 True
解法比较与面试表达 全分割版便于推导；最大词长限制减少无效枚举；记忆化搜索按需访问可达后缀，但有递归栈开销。三者都可重复用词。更大字典还可考虑 Trie，沿原字符串走边来避免反复切片。
易错点与边界复查 dp[0] 若为 False，任何首个词都接不上。 不要贪心取最长词；例如 s="cars"，词为 ["car","ca","rs"]，应选 ca+rs。 能重复用词不等于能任意排列字符；必须匹配当前位置的连续片段。 11 LeetCode 300 最长递增子序列难度：中等 ｜ 核心：结尾最优 / 严格递增 / 贪心与二分
题意与输入边界 给出非空数组，返回最长严格递增子序列的长度。可删除元素但不能改变相对顺序；不要求连续，相等值不能延长序列。
解题思路 · 状态、转移与正确性 状态定义： 基础状态 dp[i] 是必须以 nums[i] 作为最后元素的最长递增子序列长度。答案为 max(dp)，不是 dp[-1]。
dp[i]=1+max(dp[j]：j<i 且 nums[j]<nums[i])；无合法 j 时为 1
以 i 结尾的序列若长度超过 1，其前一项必位于某个 j解法一 · O(n²) 结尾 DP 每个位置枚举全部较早的下标。
from typing import List
class Solution:
def lengthOfLIS (self, nums: List [int ]) -> int :
dp = [1 ] * len (nums)
for i in range (len (nums)):
for j in range (i):
if nums[j] < nums[i]:
dp[i] = max (dp[i], dp[j] + 1 )
return max (dp)
关键代码解释 只有严格小于才能接上；等号会变成最长非递减子序列。 内层用 max 聚合所有前驱，不能只保存最后一个合法 j。 解法二 · 最小结尾 + 二分（推荐进阶） tails[k] 表示已扫描前缀中，长度为 k+1 的递增子序列的最小可能结尾。找到首个 ≥x 的位置替换；不存在则追加。
from bisect import bisect_left
from typing import List
class Solution:
def lengthOfLIS (self, nums: List [int ]) -> int :
tails = []
for x in nums:
k = bisect_left (tails, x)
if k == len (tails):
tails.append (x)
else :
tails[k] = x
return len (tails)
关键代码解释 tails 严格递增，因此可以二分。用较小的 x 替换结尾，不会损失已有长度，还会利于未来扩展。 bisect_left 找首个 ≥x；重复值替换原位，不会增加长度。 tails 各位置可能来自不同子序列，整个列表不保证是原数组的一条合法子序列；本题只求长度。 时间复杂度： O(n log n)：每个元素一次二分，末尾追加均摊 O(1)。
空间复杂度： O(n)：tails 至多 n 个元素。
示例推演 · 手算状态
[10,9,2,5,3,7,101,18] → 4；[7,7,7] → 1；[3,2,1] → 1；[1] → 1。
扫描 x tails 结尾 DP[i] 当前 LIS 长度 10 [10] 1 1 9 [9] 1 1 2 [2] 1 1 5 [2,5] 2 2 3 [2,3] 2 2 7 [2,3,7] 3 3 101 [2,3,7,101] 4 4 18 [2,3,7,18] 4 4
解法比较与面试表达 O(n²) 版本易证明，也能配合前驱数组重建路径；二分版把“每个结尾求长度”改为“每个长度求最小结尾”。重建实际 LIS 需另外维护原数组下标和前驱链。
易错点与边界复查 子序列可跳跃，子数组必须连续；不要混用最大子数组的递推。 bisect_right 会让相等元素延长序列，改变题意。 二分方案是在原位替换 tails[k]，不要 insert 导致 O(n) 移动和错误含义。 阶段验收： 从固定前驱走向枚举前驱，并学习用贪心不变量和二分改造状态。 隐去代码，独立写出本阶段各题的状态、初值、递推式，再用一个最小输入和一个反例验证。
STAGE 05 进阶算法 · 双序列动态规划使用两个前缀长度定义二维状态，比较匹配、跳过与编辑三种转移，再压缩空间。
旧左上 diag 旧上方 up 新左方 dp[j−1] 当前 dp[j] 一维压缩后，上方和左上角仍需来自旧行；左方来自当前新行。 12 LeetCode 1143 最长公共子序列难度：中等 ｜ 核心：双字符串前缀 / 匹配与跳过 / 旧左上角
题意与输入边界 给出 text1、text2，返回两者最长公共子序列长度。保持相对顺序即可，不要求连续；没有公共字符时返回 0。
解题思路 · 状态、转移与正确性 状态定义： dp[i][j] 表示 text1[:i] 与 text2[:j] 的 LCS 长度；i、j 是前缀长度，对应末字符下标 i−1、j−1。
相等：dp[i][j]=dp[i−1][j−1]+1；不等：max(dp[i−1][j],dp[i][j−1])
末字符相同时，可以在两个较短前缀的公共子序列后接上这个字符，获得最优匹配。末字符不同时不可能同时匹配它们，至少跳过其中一个，分别从上方或左方取最大。任一前缀为空时公共长度为 0。
解法一 · 二维前缀表（先掌握） 增加空前缀行与列，字符匹配时无需特殊判断边界。
class Solution:
def longestCommonSubsequence (self, text1: str , text2: str ) -> int :
m, n = len (text1), len (text2)
dp = [[0 ] * (n + 1 ) for _ in range (m + 1 )]
for i in range (1 , m + 1 ):
for j in range (1 , n + 1 ):
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 ])
return dp[m][n]
关键代码解释 字符下标减 1，dp 下标不减 1，两者含义不同。 相等时取左上角加 1；不等时不能无条件加 1。 时间复杂度： O(mn)，m、n 为两串长度。
空间复杂度： O(mn)。
解法二 · 滚动行与对角线（推荐复习） 让短字符串作为列，保存更新前的 dp[j]，并用 diag 保留旧左上角。
class Solution:
def longestCommonSubsequence (self, text1: str , text2: str ) -> int :
if len (text1) < len (text2):
text1, text2 = text2, text1
dp = [0 ] * (len (text2) + 1 )
for a in text1:
diag = 0
for j, b in enumerate (text2, 1 ):
up = dp[j]
if a == b:
dp[j] = diag + 1
else :
dp[j] = max (up, dp[j - 1 ])
diag = up
return dp[-1 ]
关键代码解释 up 是旧上方，dp[j−1] 是新左方，diag 是旧左上方。 每行 diag 重置为 0，因为空前缀列恒为 0。 diag=up 必须在本格更新之后执行，为下一列保存正确旧值。 时间复杂度： O(mn)。
空间复杂度： O(min(m,n))，含空前缀的一格；严格可写 O(min(m,n)+1)。
示例推演 · 手算状态 text1="abcde", text2="ace" → 3，公共子序列为 ace；"abc","def" → 0；"abc","abc" → 3；扩展空串边界 "","a" → 0。
text1 前缀 / text2 前缀 空 a ac ace 空 0 0 0 0 a 0 1 1 1 ab 0 1 1 1 abc 0 1 2 2 abcd 0 1 2 2 abcde 0 1 2 3
解法比较与面试表达 二维表最便于证明、画图和回溯；滚动版适合只求长度。与 LIS 相比，LCS 有两个独立前缀维度，不能直接照搬单数组二分。
易错点与边界复查 最长公共子串要求连续，失配时清零；LCS 失配应继承 max。 一维版若不保存旧左上角，匹配同一字符可能被重复计数。 返回长度与返回字符串是不同任务；重建实际 LCS 通常保留二维表回溯。 13 LeetCode 72 编辑距离难度：中等 ｜ 核心：双串前缀 / 插删替换 / 最小操作数
题意与输入边界 给出 word1、word2，允许对 word1 插入、删除或替换一个字符，每次操作代价为 1，返回转成 word2 的最少次数。空串也是合法输入。
解题思路 · 状态、转移与正确性 状态定义： dp[i][j] 表示把 word1[:i] 变成 word2[:j] 的最少操作数；空串变成 j 个字符需要 j 次插入。
dp[i][0]=i, dp[0][j]=j；相等取左上；不等取 1+min(上,左,左上)
末字符相等时可以保留，沿用两个较短前缀的代价。末字符不等时，最后一次操作分别可能是删除源串末字符、插入目标串末字符、替换源串末字符。三类操作穷尽可能，取最小值再加本次代价。
解法一 · 二维操作表（先掌握） 初始化空前缀行列，逐格比较两个末字符。
class Solution:
def minDistance (self, word1: str , word2: str ) -> int :
m, n = len (word1), len (word2)
dp = [[0 ] * (n + 1 ) for _ in range (m + 1 )]
for i in range (m + 1 ):
dp[i][0 ] = i
for j in range (n + 1 ):
dp[0 ][j] = j
for i in range (1 , m + 1 ):
for j in range (1 , n + 1 ):
if word1[i - 1 ] == word2[j - 1 ]:
dp[i][j] = dp[i - 1 ][j - 1 ]
else :
dp[i][j] = 1 + min (dp[i - 1 ][j],
dp[i][j - 1 ],
dp[i - 1 ][j - 1 ])
return dp[m][n]
关键代码解释 上方 dp[i−1][j]+1：删掉 word1 当前末字符。 左方 dp[i][j−1]+1：先得到目标较短前缀，再插入目标末字符。 左上 dp[i−1][j−1]+1：替换末字符；相等时无需 +1。 时间复杂度： O((m+1)(n+1))，非空时通常记 O(mn)；含空串时初始化也需 O(m+n)。
空间复杂度： O((m+1)(n+1))，通常简记 O(mn)。
解法二 · 滚动行（推荐复习） 短串作列，dp 初始为 0…n；每行先保存旧 dp[0]，再把当前空目标代价改为 i。
class Solution:
def minDistance (self, word1: str , word2: str ) -> int :
if len (word1) < len (word2):
word1, word2 = word2, word1
dp = list (range (len (word2) + 1 ))
for i, a in enumerate (word1, 1 ):
diag = dp[0 ]
dp[0 ] = i
for j, b in enumerate (word2, 1 ):
up = dp[j]
if a == b:
dp[j] = diag
else :
dp[j] = 1 + min (up, dp[j - 1 ], diag)
diag = up
return dp[-1 ]
关键代码解释 与 LCS 不同，空前缀列是 i，不是恒定 0；先保存 diag 再覆盖。 单位代价的插入与删除对称，因此可交换两串优化列宽。非对称加权版本不能直接交换。 时间复杂度： O(mn+m+n)，包含空串情况；非空时为 O(mn)。
空间复杂度： O(min(m,n)+1)。
示例推演 · 手算状态 word1="horse", word2="ros" → 3：horse→rorse（替换 h）→rose（删第 3 个字符 r）→ros（删 e）。"","abc" → 3；"","" → 0；"a","a" → 0。
word1 前缀 / word2 前缀 空 r ro ros 空 0 1 2 3 h 1 1 2 3 ho 2 2 1 2 hor 3 2 2 2 hors 4 3 3 2 horse 5 4 4 3
解法比较与面试表达 二维版可沿最优前驱回溯出操作序列；滚动版只保留距离。面试中先说明插、删、替换分别对应哪个前驱，再考虑压缩空间。
易错点与边界复查 初始化若全为 0，会让插入/删除空前缀错误地免费。 不要使用 len(a)+len(b)−2×LCS 代替答案；该公式仅适用于只插入删除。例 a→b：编辑距离 1，公式为 2。 编辑距离不允许交换字符作为一步；那是另一种距离定义。 阶段验收： 使用两个前缀长度定义二维状态，比较匹配、跳过与编辑三种转移，再压缩空间。 隐去代码，独立写出本阶段各题的状态、初值、递推式，再用一个最小输入和一个反例验证。
核心模板 · 按状态含义建立题目之间的联系 模板 / 代表题 状态与转移骨架 最重要的边界 相邻递推 · 509 / 70 当前 = 前一项 + 前两项 F(0)=0；爬楼梯 dp[0]=1 选或不选 · 198 前缀最优 = max(不选当前,隔一项最优+当前) 前缀长度与数组下标差 1 结尾最优 · 53 / 152 重新开始，或接在旧结尾后面 非空初始化；乘积还需最小负积 网格计数与最优 · 62 / 63 / 64 聚合上方、左方，再结合本格约束/代价 障碍清零；最小值越界为 +∞ 前缀划分 · 139 枚举最后一个分割点，OR(前缀可行且尾段合法) 空前缀 True；计入切片成本 枚举序列前驱 · 300 枚举 j 每个元素自身长度 1；全局 max 双前缀 · 1143 / 72 比较末字符，读取上、左、左上 空串行列不同；压缩需保存旧对角线
相似外观，不同语义 对照 前者 后者 最大子数组和 vs 打家劫舍 53 要连续，且状态必须以 i 结尾 198 可以跳选，状态不要求选当前 LIS vs LCS 300：一个序列，求严格递增 1143：两个序列，求共同且保序 LCS vs 编辑距离 1143：相等时 +1，不等取 max 72：相等代价不增，不等取 min+1 杨辉单行 vs 网格单行 118 依赖上一行左邻：逆序保护旧值 62 依赖本行左邻：正序使用新值 子数组 vs 子序列 子数组要求连续 子序列可删除中间元素，但保持原序
面试回答顺序 先用小例子澄清题意：是否非空、是否连续、是否严格递增，求长度还是具体方案。 口述状态含义，给出初值；用“最后一步/最后一次选择”推出递推。 说明为什么分类完整、为什么可以使用子问题的最优值。 先写易验证的版本，手算最小边界，再解释空间优化与遍历方向。 按实际代码估算复杂度，说明是否修改输入、是否包含输出与递归栈。 掌握程度自测 · 能解释，才算掌握 题目“已掌握”与下方能力自测分别记录。建议在闭卷写对、讲清转移并通过边界后再勾选。
我能区分“前 i 个的最优”与“以 i 结尾的最优” 我能解释空方案、不可达和非空最优值的不同初值 我能用负负得正说明为什么要保留最小乘积 我能解释一维数组每个位置来自旧行还是新行 我能指出 Python 切片与哈希的真实成本 我能解释 tails 的含义，以及为什么使用 bisect_left 我能独立写出 LCS 和编辑距离的旧左上角更新 我能给出转移分类完整性与最优子结构的理由
7 天学习计划 · 每天完成一个可检验目标 天数 练习内容 本日交付 Day 1 509 → 70 → 118（第一阶段） 画依赖图；解释 0 与 1 的初始化；复现三种 Fibonacci 写法 Day 2 198 → 53（第二阶段前半） 对比前缀最优与结尾最优；验证全负数组与不相邻选择 Day 3 152 + 复写第二阶段 手算一组含负数与 0 的乘积；闭卷写双状态更新 Day 4 62 → 63 → 64（第三阶段） 画二维表再压缩；测试一行、一列、障碍起点 Day 5 139 → 300（第四阶段） 解释前缀划分与枚举前驱；掌握 LIS 二分不变量 Day 6 1143 → 72（第五阶段） 手填两张 DP 表；独立实现空串边界和对角线保护 Day 7 13 题混合闭卷复习 每题先讲五步法；从 53、63、139、300、72 抽题编码，记录错误原因
复习节奏：首次做对后第 1、3、7 天各闭卷复现一次。若写不出，不急着抄答案，先判断问题来自状态定义、转移遗漏、边界、更新顺序还是语言细节。每次只针对错误原因补练。
动态规划的核心习惯：保存足够的信息，让下一次决策只依赖已经明确的状态。 公式应当是状态含义的结果，空间优化应当是依赖关系的结果。