PYTHON LESSON 106
考点精讲：区间 DP 初步
掌握区间 DP 的状态定义 dp[l][r]、分界点枚举与“短区间先算”的循环顺序，独立解决合并石子类问题。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- dp[l][r] 表示合并第 l 到 r 堆的最小代价
- 最外层枚举区间长度，再枚举左端点
- 分界点 k 把区间劈成左右两半分别合并
01 · 核心概念
区间 DP：先算短区间，再拼长区间
区间 DP：先算短区间，再拼长区间：dp[l][r] 表示把第 l 到第 r 堆合并成一堆的最小代价。单个堆根本不用合并，所以对角线 dp[i][i] 全是 0——这是白送的边界条件，建表时就已经对了。
GESP Python 7 级 · 复杂动态规划GESP Python 7 级 · 区间 DP 初步流程图是算法的表示方法，不是 Python 语法。
02 · 语法与规则
先记住这 3 条，再开始写程序
dp[l][r] 表示合并第 l 到 r 堆的最小代价先准确读出这条写法的结构与作用。
最外层枚举区间长度，再枚举左端点换一组最小数据，手工推演一次结果。
分界点 k 把区间劈成左右两半分别合并再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 区间 DP 初步：合并石子的最小总代价
piles = [4, 1, 1, 4]
n = len(piles)
# 前缀和：O(1) 算出任意一段的石子总数
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + piles[i]
def range_sum(l, r): # 第 l 到第 r 堆（含两端）的石子总数
return prefix[r + 1] - prefix[l]
INF = 10 ** 9
dp = [[0] * n for _ in range(n)] # dp[l][r]：把 l..r 合并成一堆的最小代价
for length in range(2, n + 1): # 先算短区间，再拼长区间
for l in range(0, n - length + 1):
r = l + length - 1
best = INF
for k in range(l, r): # 枚举最后一次合并的分界点
cost = dp[l][k] + dp[k + 1][r] + range_sum(l, r)
if cost < best:
best = cost
dp[l][r] = best
print("石子：", piles)
print("DP 表：")
for row in dp:
print(row)
print("最小总代价：", dp[0][n - 1])石子： [4, 1, 1, 4] DP 表： [0, 5, 8, 18] [0, 0, 2, 8] [0, 0, 0, 5] [0, 0, 0, 0] 最小总代价： 18
答案 18 与考级题库样例一致；DP 表对角线的 0 是“单堆不用合并”的免费边界。
04 · 逐步理解
每一步只解决一个问题
- 01
从网格 DP 到区间 DP
网格寻宝的状态是“走到格子 (i,j)”，区间 DP 的状态是“一段区间 [l,r]”。合并石子是它的入门招牌：n 堆石子排成一排，每次只能合并相邻两堆，代价是两堆石子总数，问全部并成一堆的最小总代价。
- 02
状态定义 dp[l][r]
dp[l][r] 表示把第 l 到第 r 堆合并成一堆的最小代价。单个堆根本不用合并，所以对角线 dp[i][i] 全是 0——这是白送的边界条件，建表时就已经对了。
dp = [[0] * n for _ in range(n)] - 03
转移：盯住最后一次合并
任何合并方案的最后一次，一定是把“左边一坨”和“右边一坨”并在一起，分界点 k 落在 l 与 r-1 之间。左右两坨各自的最小代价已经存在 dp[l][k] 和 dp[k+1][r] 里，再加上这一次的代价——整段区间的石子总和。枚举所有 k 取最小值即可。
for k in range(l, r): cost = dp[l][k] + dp[k + 1][r] + range_sum(l, r) - 04
前缀和助攻
每次转移都要算 l..r 的石子总数，逐个相加是 O(n)，塞进三重循环就拖慢一倍。提前算好前缀和，range_sum 一次减法搞定。前缀和是区间类问题的标配僚机。
prefix = [0] * (n + 1) for i in range(n): prefix[i + 1] = prefix[i] + piles[i] - 05
循环顺序：短区间先算
大区间的答案依赖小区间，所以最外层必须枚举区间长度 length 从 2 到 n，再枚举左端点 l。写反了就会读到还没算过的格子，答案全错——这是区间 DP 最容易踩的顺序坑。
for length in range(2, n + 1): for l in range(0, n - length + 1): r = l + length - 1 - 06
复杂度与考场定位
三层循环是 O(n³)，题库数据 n ≤ 200 稳稳通过。考场上看到“合并相邻”“回文区间”“括号匹配”这类词，先想区间 DP：定义 dp[l][r]、枚举分界点、短区间先算，三板斧下去就有思路。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，核对答案 18 与整张 DP 表
- 2手工推演 dp[0][1] 和 dp[1][2] 是怎么来的
- 3把石子改成 3 1 4 2，先心算再运行对照
- 4观察 DP 表：为什么只有上三角被用到
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
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) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
算法方法动态规划、贪心与分治根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。＋
正式定义
动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。
必须掌握
- DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。
- 记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。
- 滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。
- 贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。
- 归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。
- LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。
常见误区
- 状态定义不含必要信息
- 转移顺序读取到本轮新值
- 没有证明就使用贪心
- 把连续子数组和子序列混为一谈
适用边界
- 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
- DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。
编码与文本字符串、转义、切片与格式化从不可变字符序列到检索、拆分、拼接、格式化和常用判断方法。＋
正式定义
str 是不可变的 Unicode 字符序列。下标访问单个字符，切片生成新字符串；任何看似“修改字符串”的方法都会返回新对象。
必须掌握
- 下标从 0 开始，负下标从末尾开始；切片 s[start:stop:step] 不包含 stop，step 不能为 0。
- 转义序列用于在字面量中表示换行、制表、引号、反斜杠或码点；原始字符串仍有末尾反斜杠限制。
- find 找不到返回 -1，index 找不到抛 ValueError；count 统计不重叠出现次数。
- split 把字符串拆成列表，join 用一个字符串连接可迭代对象中的字符串，strip 只删除两端字符。
- f-string 的格式说明可控制宽度、对齐、精度、进制和百分比；格式化不改变原值。
- isalpha/isdigit 等按 Unicode 定义，不只识别英文字母和 ASCII 数字。
常见误区
- 尝试 s[0] = 'A' 原地修改字符串
- 把 strip('ab') 误解为删除完整子串 'ab'
- find 返回 -1 后直接拿去当有效下标
- 把字节长度与字符长度混为一谈
适用边界
- 正则表达式不在低等级字符串必修范围，但复杂模式匹配时应使用 re，而不是堆叠大量 split/find。
- 面向用户的字符计数还可能涉及组合字符和字素簇，len 统计的是 Unicode 码点序列长度。
完成检查