动态规划最常见的失败，并不是循环少写一层，而是 f[i] 从一开始就没有说清楚。有人把它描述成“前 i 个数的答案”，写到最大子数组时却返回 f[n-1]；有人为了不遗漏历史，把已经选择的全部元素塞进状态，最后得到比暴力还大的表。

本节只训练一件事：把状态写成一份可以被证明、被反驳、被代码执行的合同。

1. 状态不是变量名，而是等价类

想象两个不同的搜索过程到达同一个位置。什么时候可以把它们合并成同一个状态？答案是：从此刻开始，它们拥有完全相同的合法选择，并且这些选择产生的最优结果只由当前保存的信息决定。

DEF定义 · 状态

一个 状态 是对历史信息的压缩。所有被压缩到同一状态的历史，对于未来决策必须等价；状态值则是在指定范围和条件下要保存的可行性、最值、数量或其它量。

因此，“f[i] 表示答案”不合格；“f[i] 表示只考虑前 i 间房屋时，在不选相邻房屋的约束下可获得的最大金额”才是可检验的定义。

三个结构条件

DEF定义 · 最优子结构

若原问题的一个最优解可以由若干子问题的最优解组合得到，则问题具有最优子结构。它说明“使用子问题最优值”不会错过原问题最优值。

DEF定义 · 无后效性

给定当前状态后，未来决策不再需要知道状态没有保存的具体历史，称为无后效性。它不是说历史从未发生，而是说历史对未来的影响已经被状态完整概括。

DEF定义 · 重叠子问题

若不同递归路径会反复求解参数相同的子问题，称为重叠子问题。缓存或递推可以让每个不同状态只计算一次。

三者扮演不同角色：最优子结构支持转移正确性，无后效性支持合并历史，重叠子问题说明复用结果能带来效率收益。一个问题可以递归分解却几乎没有重叠，此时分治可能比 DP 更自然。

2. 先写“最后一步”，再命名状态

对一类求最值或计数的问题，下面的推导顺序很稳定：

1. 假设已经拿到一个完整答案；
2. 询问它的最后一步可能是什么；
3. 去掉最后一步后，剩下的是什么更小问题；
4. 找到描述这个小问题所需的最少信息；
5. 用一句话定义状态，再写转移。

这不是唯一方法。树形或记忆化问题有时更适合看“第一步决策”，背包适合看“当前物品选或不选”。关键是让所有合法方案能够按某个互斥或可控的决策被覆盖。

完整案例 1 · 爬楼梯：最后一步产生递推

题意、暴力与重叠

一次可以爬 1 级或 2 级，问到达第 n 级有多少种不同走法。最后一步只有两种：

• 从 n-1 级走 1 步；
• 从 n-2 级走 2 步。

于是暴力递归 dfs(n)=dfs(n-1)+dfs(n-2) 会形成二叉树。dfs(n-2) 同时出现在两个大分支中，重复会快速放大。

状态设计卡

问题	答案
状态语义	f[i]：恰好到达第 i 级的走法数
最后一步	走 1 级或 2 级
转移	f[i]=f[i-1]+f[i-2]
边界	f[0]=1，f[1]=1
顺序	i 从 2 递增到 n
答案	f[n]

IDEA直觉 · 为什么 `f[0]=1`

f[0]=1 表示“什么也不做”这一种空方案。它不是说第 0 级有一种跳法，而是让从第 0 级走 1 步或 2 步自然参与后续计数。计数 DP 的空方案经常是乘加规则的单位元。

手算与证明

f[0..5] 依次为 1,1,2,3,5,8。到达第 5 级的方案按最后一步分成两个互斥集合，大小分别为 f[4]=5 和 f[3]=3。

PROOF证明

所有到达 i 的方案最后一步必为 1 或 2，二者互斥且覆盖全部方案。删除最后一步后，分别与到达 i-1 和 i-2 的方案一一对应，因此方案数相加。边界给出递推的最小规模，按 i 递增时依赖均已计算。

#include <iostream>

long long countWays(int n) {
    if (n <= 1) return 1;
    long long prev2 = 1;
    long long prev1 = 1;
    for (int i = 2; i <= n; ++i) {
        const long long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

int main() {
    std::cout << countWays(5) << '\n';
}

climbing-stairs.cpp

O(·)复杂度 · 爬楼梯

状态数为 n+1，每个状态合并两个前驱，时间复杂度 $O(n)$。只依赖前两个状态，滚动变量把空间降为 $O(1)$。

WARN易错点 · 题意中的“第 0 级”

若题目把起点、第一阶或楼顶的编号定义不同，边界也会不同。不要背 f[0]=1,f[1]=1；应先写清“状态里的 i 是位置还是已经跨过的阶数”。

迁移： 若每次可走集合 steps={1,3,5}，只需让最后一步枚举 s，得到 f[i]=sum(f[i-s])。若某些台阶禁用，则这些状态的值应直接为 0。

完整案例 2 · 数字三角形：阶段、状态与决策

章节概览用“从当前位置走到底层”做了自底向上定义。这里换一个同样正确、但答案位置不同的状态，以观察状态语义如何决定边界和循环。

换成“到达当前位置”

令 f[i][j] 表示：从顶点出发，到达第 i 行第 j 个位置的最大路径和。

到达 (i,j) 的最后一步只能来自左上 (i-1,j-1) 或右上 (i-1,j)：

$$f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j])$$

三角形边缘并不同时拥有两个前驱，所以可在每行两侧加入负无穷哨兵，统一转移。

状态设计卡

问题	答案
阶段	行号 i
状态	到达 (i,j) 的最大路径和
决策	最后一步来自左上或右上
边界	f[0][0]=a[0][0]，越界前驱为 -INF
顺序	行号从小到大
答案	max_j f[n-1][j]，不是固定右下角

手算

对三角形 {2},{3,4},{6,5,7},{4,1,8,3}：

行	到达该行各点的最大和
0	2
1	5, 6
2	11, 11, 13
3	15, 12, 21, 16

底层最大值 21 才是答案。

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

long long maximumPathSum(const std::vector<std::vector<int>>& a) {
    const long long NEG = std::numeric_limits<long long>::lowest() / 4;
    const int n = static_cast<int>(a.size());
    std::vector<long long> previous(n + 1, NEG), current(n + 1, NEG);
    previous[0] = a[0][0];

    for (int i = 1; i < n; ++i) {
        std::fill(current.begin(), current.end(), NEG);
        for (int j = 0; j <= i; ++j) {
            const long long leftUp = (j > 0 ? previous[j - 1] : NEG);
            const long long rightUp = previous[j];
            current[j] = a[i][j] + std::max(leftUp, rightUp);
        }
        previous.swap(current);
    }
    return *std::max_element(previous.begin(), previous.begin() + n);
}

int main() {
    std::vector<std::vector<int>> a{{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    std::cout << maximumPathSum(a) << '\n';
}

triangle-forward-state.cpp

PROOF证明

归纳假设上一行每个状态已是到达对应位置的最优值。任何到达 (i,j) 的合法路径最后一步必来自两个可能前驱之一；选这两个前驱最优值的较大者并加当前权值，就覆盖且优于所有到达 (i,j) 的路径。最后所有完整路径终止在底层某点，因此需聚合底层最大值。

O(·)复杂度 · 正向数字三角形

状态数为 $n(n+1)/2$，每个状态常数转移，时间 $O(n^2)$；两行滚动数组空间 $O(n)$。

迁移： 同一问题可以有多个正确状态。比较“从当前位置出发”和“到达当前位置”时，不要问哪个公式更像模板；问哪个定义让边界、答案位置或方案还原更自然。

完整案例 3 · 打家劫舍：前缀最优为什么足够

题意与失败的局部规则

一排房屋各有非负金额，不能选择相邻房屋，求最大总金额。逐个选择当前金额最大的房屋并不安全，因为一次选择会封锁两个邻居；局部大小没有概括剩余约束。

暴力搜索处理第 i 间房时只有两类决策：

• 不选它，继续使用前 i-1 间房的最优值；
• 选它，则第 i-1 间不能选，只能在前 i-2 间房的最优值上加当前金额。

状态设计卡

采用前缀长度而非下标：

问题	答案
状态语义	f[i]：只考虑前 i 间房时的最大金额
当前决策	第 i 间房选或不选
转移	f[i]=max(f[i-1], f[i-2]+a[i-1])
边界	f[0]=0，f[1]=a[0]
顺序	前缀长度从小到大
答案	f[n]

为什么不需要记录“前面具体选了哪些房屋”？因为未来只关心当前房屋能否选择。选择当前房屋时，直接跳到不包含相邻房屋的前缀 i-2；这个状态已经把更早的合法选择优化完毕。

手算

金额 [2,7,9,3,1]：

i	不选第 i 间	选择第 i 间	f[i]
1	0	2	2
2	2	7	7
3	7	2+9=11	11
4	11	7+3=10	11
5	11	11+1=12	12

#include <algorithm>
#include <iostream>
#include <vector>

long long rob(const std::vector<int>& money) {
    long long fBeforePrevious = 0;
    long long fPrevious = 0;
    for (int value : money) {
        const long long current = std::max(fPrevious, fBeforePrevious + value);
        fBeforePrevious = fPrevious;
        fPrevious = current;
    }
    return fPrevious;
}

int main() {
    std::cout << rob({2, 7, 9, 3, 1}) << '\n';
}

house-robber.cpp

THM定理 · 前缀状态的充分性

对任意 i，前 i 间房的最优合法集合要么不含第 i 间房，此时价值不超过 f[i-1]；要么包含第 i 间房，此时不能含第 i-1 间房，剩余部分价值不超过 f[i-2]。两类互斥且覆盖所有合法集合，因此取最大值恰为 f[i]。

O(·)复杂度 · 打家劫舍

每间房对应一个前缀状态，每个状态比较两种决策，时间 $O(n)$；只保留前两个前缀最优值，空间 $O(1)$。

WARN易错点 · “只记当前位置”信息不足

若定义 f[i] 为“处理到房屋 i 的最大金额”，却不说明第 i 间是否被选，转移时就无法判断 i+1 能否选择。前缀最优定义之所以可行，是因为它通过 f[i-2] 显式绕开相邻冲突；另一种合法方案是使用 selected[i] 与 skipped[i] 两个末态。

迁移案例 A · 删除并获得点数

选择值 x 会获得所有 x 的总分，同时不能选择 x-1 与 x+1。先按值聚合：

$$gain[x]=x\times count[x]$$

随后值轴上的相邻冲突与房屋相邻冲突完全相同：

$$f[x]=max(f[x-1],f[x-2]+gain[x])$$

变化的不是递推骨架，而是“房屋位置”被映射成“数值”。时间复杂度为 $O(n+U)$，其中 U 是最大值；值域很大时应排序离散值，避免盲开大数组。

迁移案例 B · 环形打家劫舍

首尾也相邻，使线性前缀多出一个全局约束。任意合法方案不可能同时选择首尾，于是拆成两个覆盖全部情况的线性问题：

• 不考虑最后一间：区间 [0,n-2]；
• 不考虑第一间：区间 [1,n-1]。

两者最大值即答案。这里的迁移技巧是把难以写进局部转移的互斥条件拆成有限个线性情形。单房屋需单独处理，避免两个空区间。

完整案例 4 · 最大子数组和：f[n-1] 为什么不是答案

题意与状态选择

给定整数数组，选择一个非空连续子数组，使元素和最大。若直接定义“前 i 个数中的最大子数组和”，最后一步不容易写：最优子数组可能早已结束，也可能延伸到当前位置。

改问一个更强的局部条件：

f[i] 表示必须以位置 i 结尾的非空连续子数组最大和。

此时向左看只有两种可能：

• 前面的最佳结尾和为正，接上 a[i]；
• 前面的和无益，从 a[i] 重新开始。

$$f[i]=max(a[i],f[i-1]+a[i])$$

状态设计卡

问题	答案
状态语义	f[i]：以 i 结尾的非空连续子数组最大和
决策	延长前一个结尾，或从当前元素重新开始
边界	f[0]=a[0]；数组必须非空
顺序	i 从 1 到 n-1
答案	max_i f[i]，不是 f[n-1]

最小反例

数组 [5,-100,1] 中：

• f[0]=5；
• f[1]=-95；
• f[2]=1。

若返回 f[2]，会得到 1；全局答案却是 5。原因不是转移错误，而是状态只承诺“以 i 结尾”。

#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

long long maximumSubarray(const std::vector<int>& a) {
    if (a.empty()) throw std::invalid_argument("array must be non-empty");
    long long endingHere = a[0];
    long long answer = a[0];
    for (std::size_t i = 1; i < a.size(); ++i) {
        endingHere = std::max<long long>(a[i], endingHere + a[i]);
        answer = std::max(answer, endingHere);
    }
    return answer;
}

int main() {
    std::cout << maximumSubarray({-2, 1, -3, 4, -1, 2, 1, -5, 4}) << '\n';
}

maximum-subarray.cpp

PROOF证明

任意以 i 结尾的非空连续子数组，要么只含 a[i]，要么由某个以 i-1 结尾的连续子数组再接上 a[i]。第二类要取得最大值，前半段必须取 f[i-1]。两类取最大得到 f[i]。任意非空连续子数组都有唯一右端点，所以对所有 f[i] 取最大覆盖全部候选。

O(·)复杂度 · 最大子数组

共有 n 个结尾状态，每个状态常数转移，时间 $O(n)$。只保存前一状态与全局聚合值，空间 $O(1)$。

WARN易错点 · 全负数组不能把答案初始化为零

题目要求子数组非空时，0 可能根本不是合法方案。把 endingHere 和 answer 初始化为首元素，才能让 [-5,-2,-7] 返回 -2。

迁移： 若要求返回区间端点，在“从当前元素重新开始”时记录新左端点，在更新全局答案时保存当前左右端点。状态值解决最优数值，附加前驱/端点解决方案还原。

3. 两类状态设计反例

信息不足：不同未来被错误合并

假设股票题允许持有一股，但只记录 f[i] 为“第 i 天最大利润”，没有记录收盘时是否持股。两个利润相同的历史，一个持股、一个空仓，下一天可执行的动作完全不同；它们不能合并。

修复方式是增加有限历史状态，例如 cash[i] 与 hold[i]。这不是“多开一维更保险”，而是恢复无后效性所需的最少信息。

信息过多：状态退化为完整历史

打家劫舍若用位掩码记录前面每间房是否被选，会有 $2^n$ 个历史。未来实际只关心相邻冲突，完整掩码保存了大量无关信息。

ANTI反例 · 过多信息也会破坏算法

“状态信息越多越安全”只保证不丢信息，却不保证可计算。动态规划的目标不是保存历史，而是找到使未来等价的最小摘要。信息不足导致错误合并，信息过多导致状态爆炸。

4. 从状态语义检查答案位置

做完转移后，用下面三问避免“表算对了，返回错了”：

1. 状态是否已经覆盖完整问题？前缀最优 f[n] 通常可以直接返回。
2. 状态是否附带末尾条件？“以 i 结尾”通常需要对所有末态聚合。
3. 是否有多个合法终止状态？状态机、网格边界和剩余容量题常需取若干末态的最大/最小/和。

状态例子	答案位置
前 i 间房最大收益	f[n]
以 i 结尾的最大子数组	max_i f[i]
到达三角形 (i,j) 的最大和	max_j f[n-1][j]
恰好凑出金额 x 的最少硬币	f[target]，但先判断是否可达

5. 本节复盘卡

看到一道新题，先口述而不是先敲 vector<int> dp：

• 我正在优化/计数的对象是什么？
• 状态限定的范围是前缀、结尾、区间、位置还是剩余资源？
• 哪些历史可以安全合并？哪些未来差异迫使我增加维度？
• 最后一步是否把所有合法方案分成了覆盖且可控的类别？
• 边界是一个真实小问题的答案，还是为了让公式“看起来能跑”而随手填的？
• 最终答案与状态语义是否完全一致？

纸上练习

分别为“最长递增子序列”和“最长公共子序列”写一句状态语义，不写转移。比较它们为什么一个常用“以 i 结尾”，另一个常用“双前缀”。如果状态语义无法自然说出口，暂时不要写代码。

下一节从记忆化搜索到递推会把本节的状态合同映射到递归参数、备忘录维度和循环顺序。你会看到：两种写法不是两个算法，而是同一张状态依赖图的两种求值方式。

参考与训练入口

• OI Wiki：动态规划基础：阶段、状态、决策、最优子结构与无后效性的系统说明。
• 灵茶山艾府：动态规划题单：可按入门 DP、网格图 DP 与经典线性 DP 继续选择同模型练习。
• 本节代码和推导为本站独立编写；外部题目只作为训练入口，不复制原题解。