PYTHON LESSON 102
网格寻宝
掌握二维 DP 的状态定义与转移，会用滚动数组把空间压缩到一行。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- dp[i][j] 表示走到 (i,j) 的最大收益
- dp[i][j] = max(上方, 左方) + 本格
- 滚动一维数组：dp[j] 逐行覆盖更新
01 · 核心概念
二维动态规划：路径最值
二维动态规划：路径最值：二维 DP 的状态 dp[i][j] 回答：从起点走到 (i,j)，最多能拿多少金币？把“整个网格的最优走法”拆成 m×n 个小问题，每个小问题只依赖左边和上边的答案。
GESP Python 7 级 · 二维动态规划GESP Python 7 级 · 最值优化同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
02 · 语法与规则
先记住这 3 条，再开始写程序
dp[i][j] 表示走到 (i,j) 的最大收益先准确读出这条写法的结构与作用。
dp[i][j] = max(上方, 左方) + 本格换一组最小数据，手工推演一次结果。
滚动一维数组：dp[j] 逐行覆盖更新再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 网格寻宝：二维 DP 求最大金币和
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1],
]
m = len(grid)
n = len(grid[0])
# dp[i][j]：从起点走到 (i,j) 最多能拿多少金币
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
best = 0
if i > 0:
best = max(best, dp[i - 1][j]) # 从上方来
if j > 0:
best = max(best, dp[i][j - 1]) # 从左方来
dp[i][j] = best + grid[i][j]
print("金币地图：")
for row in grid:
print(row)
print("DP 表（每格存走到这里的最大和）：")
for row in dp:
print(row)
print("最多能拿到", dp[m - 1][n - 1], "枚金币")金币地图： [1, 3, 1] [1, 5, 1] [4, 2, 1] DP 表（每格存走到这里的最大和）： [1, 4, 5] [2, 9, 10] [6, 11, 12] 最多能拿到 12 枚金币
DP 表的每个格子都是“走到这里的最优解”，右下角的 12 就是最终答案。
04 · 逐步理解
每一步只解决一个问题
- 01
状态：站在每个格子上问一个问题
二维 DP 的状态 dp[i][j] 回答：从起点走到 (i,j)，最多能拿多少金币？把“整个网格的最优走法”拆成 m×n 个小问题，每个小问题只依赖左边和上边的答案。
dp = [[0] * n for _ in range(m)] - 02
转移：只能从两个方向来
走到 (i,j) 的最后一步，要么从上方 (i-1,j) 下来，要么从左方 (i,j-1) 过来。取两者中较大的，加上本格金币，就是 dp[i][j]。这就是状态转移方程。
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] - 03
边界：第一行与第一列没得选
第一行只能从左边来，第一列只能从上边来，所以转移前用 if i > 0、if j > 0 判断方向是否存在。起点 dp[0][0] 就是它自己的金币数。
best = 0 if i > 0: best = max(best, dp[i - 1][j]) if j > 0: best = max(best, dp[i][j - 1]) - 04
滚动数组：空间压到一行
算第 i 行时只用得到第 i-1 行，更早的行可以扔掉——于是 dp 只留一行，从左到右覆盖更新：dp[j] 还没更新时是“上方”，dp[j-1] 刚更新过是“左方”。空间从 O(mn) 降到 O(n)，这就是滚动数组思想。
dp = [0] * n for i in range(m): for j in range(n): dp[j] = max(dp[j], dp[j - 1] if j > 0 else 0) + grid[i][j] - 05
路径数与区间 DP 预告
把 max 换成加法，同样的骨架就能算“从起点到终点有多少种走法”（路径计数）。而“区间 DP”是另一种二维 DP：dp[l][r] 表示一段区间上的最优解（比如合并一堆石子的最小代价），先算短区间再拼长区间——思路相通，留给你探索。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，对照金币地图检查 DP 表
- 2手工推导 DP 表的第一行和第一列
- 3改一个格子的金币数，看最优值怎么变
- 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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
完成检查