动态规划 · HTML
数学 / 逻辑形态
dp[r][c] 表示到达 (r,c) 或从其出发的答案；例如只向右/下时，dp[r][c]=cell(r,c) ⊕ Aggregate(dp[r-1][c],dp[r][c-1])。遍历顺序必须拓扑兼容。
识别信号
- 状态天然是二维坐标。
- 移动方向受限，依赖图无环。
- 大量路径共享相同格子后缀/前缀。
- 目标是路径计数、最小代价或最大收益。
- 每格只依赖固定方向的邻格。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 允许四向任意循环 | 普通表格顺序不再是拓扑序；最短路用 BFS/Dijkstra，计数需其他结构。 |
| 只问连通可达 | 无需聚合路径价值时，DFS/BFS 更自然。 |
| 路径瓶颈目标 | 若可四向且代价为路径最大值，可能是 minimax Dijkstra 或答案二分。 |
核心不变量
处理 (r,c) 时，它依赖的所有邻格状态已符合定义；写入后 dp[r][c] 汇总了所有合法进入方式且无遗漏重复。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 坐标 (r,c) 的最优值/计数；障碍格用不可达 sentinel。 |
| Transition | 从所有合法前驱取 min/max/sum，再结合当前格贡献；起点独立初始化。 |
| Frontier / order | 与移动方向一致的行列拓扑序；若只依赖上一行和当前行左侧，可压成一维。 |
Python 骨架
def min_grid_cost(grid):
if not grid or not grid[0]: return 0
rows, cols = len(grid), len(grid[0])
dp = [float('inf')] * cols
dp[0] = 0
for r in range(rows):
for c in range(cols):
from_up = dp[c]
from_left = dp[c - 1] if c else float('inf')
if r == 0 and c == 0:
dp[c] = grid[r][c]
else:
dp[c] = grid[r][c] + min(from_up, from_left)
return dp[-1]
正确性思路
- 起点状态按唯一路径正确初始化。
- 拓扑顺序保证上方与左方已是正确子答案。
- 任一路径进入当前格的最后一步必来自一个合法前驱，取最优并加当前代价既完备又不漏；归纳到终点。
复杂度
| Time | Space | Parameters |
|---|
| O(RC) | O(C) 压缩；完整表 O(RC) | R/C 为行列数；依赖半径更大时空间相应增加。 |
边界条件
- 空网格
- 单行/单列
- 起点或终点障碍
- 不可达 sentinel 与加法
- 负权但 DAG 仍可 DP
- 压缩时读写顺序
错误模式
| Pattern | Why it fails / fix |
|---|
| 遍历方向与依赖相反 | 读取到本轮未计算或已覆盖状态；先画依赖箭头。 |
| 首行首列到处特判 | sentinel 或额外边界可统一转移，减少分支。 |
| 把循环网格当 DAG | 四向移动产生环时，单次扫描无法保证状态最终。 |
| 一维压缩覆盖上方值 | 更新前明确 dp[c] 是旧行，dp[c-1] 是新行。 |
选择与排除规则
- 先确认移动依赖是否无环。
- 定义状态是到达还是出发，并选择相应遍历方向。
- 用 sentinel 统一边界与不可达。
- 只在依赖半径明确后压缩空间。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最小代价路径经过左下，总成本 6。 |
| Setup | 代价网格 [[2,5],[1,3]]，只向右或下。 |
| Trace | 到左下为 3，到右上为 7；右下取 min(3,7)+3=6。 |
Recall prompts
我的补充