动态规划 · HTML
数学 / 逻辑形态
dp[l][r] 表示闭区间 [l,r] 的最优值/计数。按长度递增，枚举 k：dp[l][r]=Aggregate_k(Combine(dp[l][k],dp[k+1][r],local(l,k,r)))，或由去掉一端的状态转移。
识别信号
- 子问题由连续区间 [l,r] 唯一描述。
- 最后一步把区间拆成两个更短区间或移除一个端点。
- 合并次序、括号化、回文或成对消除影响答案。
- 相同子区间会出现在多种外层决策中。
- 需枚举区间长度与内部切分点。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 独立不相交区间选择 | 若只按端点选择兼容区间，排序贪心或 weighted interval DP 更直接。 |
| 任意子集而非连续区间 | 两个端点不能表达被挖空的集合，需 bitmask/其他状态。 |
| 局部合并代价固定且可贪心 | 若有可证明的交换规则，不必承担 O(n³) 区间 DP。 |
核心不变量
计算长度 len 的区间前，所有更短依赖区间均已正确；dp[l][r] 枚举了该区间所有合法最后动作。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 闭区间端点 (l,r) 的最优值/方案数；可保存 split[l][r] 重构结构。 |
| Transition | 枚举最后分割 k 或两端配对/删除动作，把更短区间答案与局部代价组合。 |
| Frontier / order | 区间长度从短到长；同长度内 l 任意，r=l+len-1。 |
Python 骨架
def min_merge_cost(values):
n = len(values)
if n <= 1: return 0
prefix = [0]
for x in values: prefix.append(prefix[-1] + x)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for l in range(n - length + 1):
r = l + length - 1
total = prefix[r + 1] - prefix[l]
dp[l][r] = min(
dp[l][k] + dp[k + 1][r] + total
for k in range(l, r)
)
return dp[0][n - 1]
正确性思路
- 长度 0/1 无需合并，base 正确。
- 任一完整合并结构都有唯一最后一次分割 k，其两侧是更短区间。
- 归纳假设两侧最优，枚举全部 k 后取最优，既不漏结构也不会比真正最优差。
复杂度
| Time | Space | Parameters |
|---|
| 典型 O(n³)，若转移可优化则可能 O(n²) | O(n²) | n 为序列长度；每区间枚举 O(n) 个 split。 |
边界条件
- 空/单元素
- 闭区间端点
- 长度循环起点
- 局部代价的前缀和
- 不可达状态 sentinel
- 恢复多个同优 split
错误模式
| Pattern | Why it fails / fix |
|---|
| 按 l/r 自然顺序填表 | 大区间可能读到尚未计算的短区间；应按长度拓扑序。 |
| split 边界重叠或漏项 | 若左为 [l,k]，右必须是 [k+1,r]，且 k 范围 l..r-1。 |
| 把局部总代价重复/漏加 | 明确代价属于最后一次合并还是子问题内部。 |
| 轻率声称 O(n²) | n² 个区间再枚举 n 个 k，默认是 O(n³)。 |
选择与排除规则
- 先写最后一次动作如何切分区间。
- 按长度保证所有依赖更短。
- 用 prefix O(1) 计算区间聚合。
- O(n³) 过大时再检查单调性/四边形不等式等优化条件。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | dp[0][2]=9，最后 split 在第二堆之后。 |
| Setup | 三堆重量 [2,1,3]，相邻两堆合并代价为新堆总重。 |
| Trace | 先合 2+1 成本 3，再与 3 合成本 6，总 9；另一顺序为 4+6=10。 |
Recall prompts
我的补充