PYTHON LESSON 104
七级综合：LCS 与背包入门
掌握 LCS 的二维 DP 与滚动数组优化，理解 0-1 背包“选/不选”的决策模型。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- 字符相等：dp[j] = 左上 + 1；不等：max(上, 左)
- prev, cur = cur, prev 两行滚动
- 背包容量倒序枚举：for j in range(W, w-1, -1)
01 · 核心概念
LCS、0-1 背包与滚动数组
LCS、0-1 背包与滚动数组：dp[i][j] 表示“a 的前 i 个字符”和“b 的前 j 个字符”的最长公共子序列长度。和网格寻宝一样，每个状态只依赖上、左、左上三个邻居——二维 DP 的家族面孔。
GESP Python 7 级 · 最长公共子序列 LCSGESP Python 7 级 · 滚动数组空间优化GESP Python 7 级 · 综合应用同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
02 · 语法与规则
先记住这 3 条，再开始写程序
字符相等：dp[j] = 左上 + 1；不等：max(上, 左)先准确读出这条写法的结构与作用。
prev, cur = cur, prev 两行滚动换一组最小数据，手工推演一次结果。
背包容量倒序枚举：for j in range(W, w-1, -1)再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 七级综合：LCS + 0-1 背包（滚动数组实战）
# ① 最长公共子序列：两行滚动数组
a = "ABCBDAB"
b = "BDCABA"
m = len(b)
prev = [0] * (m + 1)
cur = [0] * (m + 1)
for ca in a:
for j in range(m):
if ca == b[j]:
cur[j + 1] = prev[j] + 1 # 对上：左上角 + 1
else:
cur[j + 1] = max(prev[j + 1], cur[j]) # 没对上：取上方或左方
prev, cur = cur, prev
print(f"字符串 {a} 和 {b} 的 LCS 长度：{prev[m]}")
# ② 0-1 背包：一维滚动数组
items = [(2, 3), (3, 4), (4, 5), (5, 6)] # (重量, 价值)
W = 5
dp = [0] * (W + 1) # dp[j]：容量 j 能装的最大价值
for w, v in items:
for j in range(W, w - 1, -1): # 倒序！保证每件只用一次
dp[j] = max(dp[j], dp[j - w] + v)
print(f"背包容量 {W}，最大价值：{dp[W]}")字符串 ABCBDAB 和 BDCABA 的 LCS 长度：4 背包容量 5，最大价值：7
两段代码共用同一个思想：只保留“上一行”的 DP 值，滚动覆盖更新。
04 · 逐步理解
每一步只解决一个问题
- 01
LCS 的状态定义
dp[i][j] 表示“a 的前 i 个字符”和“b 的前 j 个字符”的最长公共子序列长度。和网格寻宝一样，每个状态只依赖上、左、左上三个邻居——二维 DP 的家族面孔。
- 02
LCS 的两种转移
比较 a[i-1] 和 b[j-1]：相等，说明这个字符可以进公共序列，dp[i][j] = 左上 + 1；不等，说明至少一个用不上，取“上方”和“左方”的较大值。
if ca == b[j]: cur[j + 1] = prev[j] + 1 else: cur[j + 1] = max(prev[j + 1], cur[j]) - 03
两行滚动省空间
算第 i 行只用第 i-1 行，于是只保留 prev、cur 两行，算完一行就交换角色。prev, cur = cur, prev 一步完成“新行变旧行”，空间从 O(nm) 降到 O(m)，2000×2000 也毫无压力。
prev, cur = cur, prev - 04
0-1 背包的决策模型
每件装备只有一次机会：选，或不选。dp[j] 表示容量 j 时的最大价值：不选第 i 件就是原来的 dp[j]；选就是 dp[j-w] + v（腾出 w 的容量装它）。两者取大。
dp[j] = max(dp[j], dp[j - w] + v) - 05
为什么容量必须倒序
一维数组里 dp[j-w] 如果已经装过当前这件物品，正序枚举就会把它再装一次（变成“无限背包”）。倒序从大到小更新，dp[j-w] 还是上一轮（没装过它）的旧值，每件恰好用一次。这是背包问题最容易踩的坑。
for j in range(W, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) - 06
七级终点也是新起点
至此你已集齐：哈希表、图的存储与遍历、泛洪、二维 DP、LIS/LCS、背包与滚动数组。配套挑战题一道是标准 0-1 背包，一道是无权图单源最短路（BFS 逐层标距离）——都是把本单元积木搭成大楼的综合演练。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，核对 LCS 长度与背包价值
- 2手工画出 3×3 的 LCS 小表格
- 3把背包容量改成 6，预测新答案
- 4把背包的倒序改成正序，想想会出什么事
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
完成检查