PYTHON LESSON 088
六级综合：爬楼梯与数字三角形
理解动态规划“大问题拆小问题、记住算过的答案”的思想，会写一维递推和数字三角形两类入门 DP。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- f[i] = f[i-1] + f[i-2] 状态转移
- 列表当“备忘录”存中间结果
- 自底向上：从最后一行倒推回顶端
01 · 核心概念
简单动态规划
简单动态规划：动态规划（DP）= 把大问题拆成同形状的小问题 + 把算过的答案存进“备忘录”，绝不重算。每个 DP 题都要回答三问：状态是什么（f[i] 表示什么）？转移是什么（f[i] 由谁算出来）？按什么顺序算？
GESP Python 6 级 · 简单动态规划GESP Python 6 级 · 综合应用有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
f[i] = f[i-1] + f[i-2] 状态转移先准确读出这条写法的结构与作用。
列表当“备忘录”存中间结果换一组最小数据，手工推演一次结果。
自底向上：从最后一行倒推回顶端再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 六级综合：爬楼梯 + 数字三角形（简单动态规划）
# ① 爬楼梯：每次可以跨 1 级或 2 级台阶
n = 10
f = [0] * (n + 1)
f[1] = 1
f[2] = 2
for i in range(3, n + 1):
f[i] = f[i - 1] + f[i - 2]
print("爬", n, "级台阶共有", f[n], "种爬法")
# ② 数字三角形：从顶端走到底部，求最大路径和
tri = [
[7],
[3, 8],
[8, 1, 0],
[2, 7, 4, 4],
[4, 5, 2, 6, 5],
]
best = tri[4][:] # 先复制最底行
for row in range(3, -1, -1):
for j in range(len(tri[row])):
best[j] = tri[row][j] + max(best[j], best[j + 1])
print("数字三角形最大路径和：", best[0])爬 10 级台阶共有 89 种爬法 数字三角形最大路径和： 30
两道题的共同套路：定义状态、写出转移、确定递推顺序——动态规划三板斧。
04 · 逐步理解
每一步只解决一个问题
- 01
什么是动态规划
动态规划（DP）= 把大问题拆成同形状的小问题 + 把算过的答案存进“备忘录”，绝不重算。每个 DP 题都要回答三问：状态是什么（f[i] 表示什么）？转移是什么（f[i] 由谁算出来）？按什么顺序算？
- 02
爬楼梯的状态转移
最后一步只有两种可能：从第 i-1 级跨 1 步上来，或从第 i-2 级跨 2 步上来。所以 f[i] = f[i-1] + f[i-2]。初始 f[1]=1、f[2]=2 是递推的地基，地基错了整栋楼都歪。
f = [0] * (n + 1) f[1] = 1 f[2] = 2 for i in range(3, n + 1): f[i] = f[i - 1] + f[i - 2] - 03
先手算，再上机
f[3]=3、f[4]=5、f[5]=8……正是斐波那契数列。先在小数据上手算验证转移式，再让程序跑大数据——DP 调试的第一步永远是人机对账。
- 04
数字三角形为什么倒着推
从顶端往下走时，每个格子有两个选择，很难预判哪条更优；反过来从底行向上推：每个格子的最优值 = 自己的数 + 下一层两个相邻最优值中较大的那个。子问题先算好，大问题的答案自然浮现。
best[j] = tri[row][j] + max(best[j], best[j + 1]) - 05
滚动数组省空间
best 只有一行长：推完一行就覆盖旧值，因为更下面的行已经没用了。这种“只保留需要的一行”的写法叫滚动数组，是七级还要深入的空间优化思想。
best = tri[4][:] for row in range(3, -1, -1): for j in range(len(tri[row])): best[j] = tri[row][j] + max(best[j], best[j + 1]) - 06
六级综合挑战
配套挑战题把本单元串了起来：一道要重建二叉树再做层序遍历（树的解析 + BFS），一道把爬楼梯升级成每次可跨 1~3 级并对 10^9+7 取模（三阶递推 + 滚动变量）。先画状态转移图，再动手写代码。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，核对 10 级台阶的 89 种爬法
- 2手算 5 级台阶的爬法再和程序对照
- 3在数字三角形上画出最大和路线
- 4说说两个程序里“备忘录”分别是什么
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
Python 基础程序执行、输入输出、变量与数据类型从一条语句怎样执行开始，系统掌握 print、input、变量、对象、类型与显式转换。＋
正式定义
Python 程序由语句和表达式组成，通常按从上到下的顺序执行。变量名通过赋值绑定到对象；对象有类型和值。input() 始终返回 str，是否转换成 int 或 float 必须由题意决定。
必须掌握
- print(*objects, sep=' ', end='\n') 可以控制对象之间的分隔符和末尾字符。
- input(prompt) 读取一行并去掉行末换行符，返回值一定是字符串。
- 赋值符号 = 建立或更新名字与对象的绑定；== 才是相等比较。
- 核心标量类型包括 int、float、bool、str 和 NoneType；bool 是 int 的子类，但语义上应当用于真假判断。
- int、float、str、bool 可做显式类型转换；转换可能失败，不能把任意文本直接当数字。
- 注释以 # 开始；规范的变量名应表达含义，不能使用关键字。
常见误区
- 把 input() 的结果直接与整数相加
- 混淆 = 与 ==
- 用 float 表示必须精确的十进制金额却不考虑误差
- 变量名覆盖 print、list 等内置名称
适用边界
- 课程先讲同步的文本输入输出；文件、网络、图形界面和异步输入分别在对应章节说明。
- Python 的变量没有固定类型，但对象有类型；这不等于程序可以随意混用类型。
完成检查