阅读导航
1. 第一章：动态规划入门与记忆化搜索，例题 L1。
2. 第二章：递推与基础概念，例题 L2—L8。
3. 第三章：状态对照、初始化、计算顺序、空间优化与方案还原。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第一章 动态规划入门与记忆化搜索
动态规划会把重复出现、后续条件相同的子问题整理成状态，并保存它们的答案。本章先从已经熟悉的递归搜索出发，观察重复计算，再用记忆化保存结果；记忆化搜索在本篇属于动态规划的实现方式。
1. 例题 L1：路线方案计数
题目
一条路线从位置 000 到位置 nnn。每次只能前进 111 格或 333 格，不能超过终点。不同移动顺序算不同方案，求到达 nnn 的方案数，对 100000000710000000071000000007 取模。
* 普通递归演示：0≤n≤300\le n\le 300≤n≤30。
* 记忆化演示：0≤n≤10000\le n\le 10000≤n≤1000。
* 递推实现：0≤n≤1000000\le n\le 1000000≤n≤100000。
n=5n=5n=5 时答案为 444：
n=0n=0n=0 时，不移动也算 111 种方案。
1.1 递归状态与转移
设 dfs(r)\mathrm{dfs}(r)dfs(r) 返回：还剩 rrr 格时，有多少种走法。
第一步如果走 111 格，后续有 dfs(r−1)\mathrm{dfs}(r-1)dfs(r−1) 种；如果走 333 格，后续有 dfs(r−3)\mathrm{dfs}(r-3)dfs(r−3) 种。两类方案第一步不同，互不重叠，所以可以相加。
边界为：
* r=0r=0r=0：恰好完成，返回 111。
* r<0r<0r<0：越过终点，返回 000。
1.2 普通递归的核心代码
调用方式： 使用小范围 nnn，计算 dfs(n)\mathrm{dfs}(n)dfs(n)。
1.3 重复子问题
取 n=4n=4n=4，把普通递归展开成决策树。为便于阅读，只画剩余距离非负的合法分支；越过终点的分支返回 000，不在图中展开。
右侧的“剩余 111 格”来自第一步走 333 格；左侧的“剩余 111 格”来自连续走了三次 111 格。它们处在不同决策路径下，但后续问题相同：还剩 111 格，只有走 111 格这一种完成方式。
普通 DFS 会分别展开这两个节点。记忆化则让第一次计算得到的 dfs(1)=1\mathrm{dfs}(1)=1dfs(1)=1 被保存，第二次需要时直接取用。
这里要区分两件事：前面已经走出的过程不同，完整方案仍然不同；需要复用的是后续子问题的计算结果。如果题目只问总数量，就不必重复展开完全相同的后续过程。
1.4 记忆化核心代码
调用方式： done\mathrm{done}done 初始为全 false\mathrm{false}false，答案为 dfs(n)\mathrm{dfs}(n)dfs(n)。若在同一程序中处理新测试，需重新初始化对应记忆化数据。
这里用 done\mathrm{done}done 区分“没算过”和“答案恰好为 000”。即使方案数取模后为 000，也不应该当作没算过而反复展开。
每个非负 rrr 状态只需要真正计算一次，时间 O(n)O(n)O(n)，数组与递归栈空间 O(n)O(n)O(n)。
1.5 记忆化结果的使用
dfs(r)\mathrm{dfs}(r)dfs(r) 返回的是这个后续问题的方案数。如果不同前缀都来到同一个 rrr，它们都要把该方案数加入各自结果，只是无需重新展开计算。
若只是发现 rrr 见过便直接返回 000，就可能把不同前缀能够形成的方案一起删掉。
决策树中的多个 F(1)F(1)F(1) 节点在这里共用一个计算结果；F(0)F(0)F(0) 也只保留一个状态。它不再是一棵每个节点只有一个父节点的树，而是一张可以被不同状态共同依赖的图。
在本题中，每次依赖的剩余距离都会减小，不会绕回原状态，因此这张图没有环。我们既可以沿依赖递归求解并保存答案，也可以先求小状态，再依次求大状态。
例如 F(0)=1F(0)=1F(0)=1、F(1)=1F(1)=1F(1)=1、F(2)=1F(2)=1F(2)=1、F(3)=2F(3)=2F(3)=2，所以 F(4)=F(3)+F(1)=3F(4)=F(3)+F(1)=3F(4)=F(3)+F(1)=3。三种完整走法是 1+1+1+11+1+1+11+1+1+1、1+31+31+3、3+13+13+1；复用 F(1)F(1)F(1) 不会把后两种走法合成同一种方案。
1.6 记忆化的适用条件
以“同一条路线不能重复经过格子”的迷宫路径计数为例：
* 两条路线到达相同格子。
* 但一条路线用过左边的格子，另一条用过上边的格子。
* 接下来可选路径可能不同。
仅用位置 (x,y)(x,y)(x,y) 不足以确定答案，不能直接设置 f[x][y]f[x][y]f[x][y] 记忆化。
另外，本例 rrr 持续减小，没有循环依赖。一般有环状态不能简单标记为“已算过”就读取答案，否则可能读到尚未计算完成的值。递归深度过大还可能导致栈溢出；记忆化不等于适合无限增大 nnn。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二章 基础线性动态规划
2. 动态规划的递推实现
仍然看 L1。既然剩余 rrr 的答案只依赖更小的数，就可以直接先算小的，再算大的。
对照上一节的状态依赖图，这个顺序就是先得到 F(0)F(0)F(0)，再求 F(1)F(1)F(1)、F(2)F(2)F(2)、F(3)F(3)F(3)……每次需要的较小状态都已经完成。这样就把“沿决策树向下尝试”的过程，转成了“按依赖顺序计算状态”。
也可以换一个等价角度，定义：
> dp[i]\mathrm{dp}[i]dp[i]：从位置 000 到达位置 iii 的方案数。
按最后一步分类：
* 最后走 111 格：来自 i−1i-1i−1。
* 最后走 333 格：来自 i−3i-3i−3。
于是：
dp[i]=dp[i−1]+dp[i−3]\mathrm{dp}[i]=\mathrm{dp}[i-1]+\mathrm{dp}[i-3] dp[i]=dp[i−1]+dp[i−3]
不存在的负下标来源按 000 处理。
2.1 递推核心代码
调用方式： 读入 nnn 后，答案为 countWays()。
iii 000 111 222 333 444 555 666 dp[i]\mathrm{dp}[i]dp[i] 111 111 111 222 333 444 666
时间 O(n)O(n)O(n)，空间 O(n)O(n)O(n)。
记忆化和递推不是两套不同的数学原理。两者复用了子问题答案，区别主要在计算的组织方式：前者沿着依赖递归求解，后者直接安排好顺序。
3. 线性动态规划的基本概念
前面的路线计数题中，我们没有把每一种完整走法都重新走一遍，而是记录“到达每个位置有多少种走法”，再利用已经算出的结果，计算其他位置的答案。
动态规划的一个重要做法，就是先解决一些小问题，把答案记下来，再用它们解决更大的问题。
本篇学习的线性动态规划，常常处理这样的问题：
* 一条路线：考虑到达第 111 个、第 222 个位置时的答案。
* 连续几天的安排：考虑前 111 天、前 222 天的答案。
* 一串数字：考虑前几个数字，或者以某个数字结尾时的答案。
这些问题都有一定的先后顺序。写成递推时，要先算出当前需要用到的结果，再继续计算。
这里的“线性”不表示程序只能写一层循环，也不表示只能用一维数组。有时计算一个位置的答案，需要比较前面很多位置，时间可能是 O(n2)O(n^2)O(n2)；有时还要多记一项信息，例如“到了第几天、今天选了哪种活动”，就可能使用二维数组。后面的例题会逐步说明。
3.1 状态设计
“状态”这个词看起来抽象，可以先把它理解为：我们现在要解决的是哪一个小问题？
例如，在路线计数题中，可以写：
> dp[i]\mathrm{dp}[i]dp[i]：从起点走到位置 iii，一共有多少种走法。
这里，下标 iii 告诉我们“走到哪里”；数组中存放的数，告诉我们“有多少种走法”。所以，写 dp[i]\mathrm{dp}[i]dp[i] 之前，要先说清楚这两件事。
那么，要不要把前面具体怎么走都记下来呢？这要看题目的要求。
如果求方案数，就要把不同的合法走法都计入。 只要后面允许的走法只由当前位置决定，就可以先记下到达这里的方案数，继续计算，不必逐条保存完整路线。
如果求最小花费，有些较差的走法就不必保留。 例如，每次只能前进 111 或 222 个位置，费用只由落在哪个位置决定。两条路线都到达位置 555，一条已经花了 777 元，另一条花了 101010 元。接下来，两条路线能采用相同的走法，支付相同的费用，因此只保留花费 777 元的结果就够了。
但如果题目中还有一张只能使用一次的优惠券，两条路线到达同一位置时，一条已经用过，另一条还没用过，后面的花费就可能不同。此时除了位置，还要记录“优惠券是否已经使用”。
因此，设计状态时可以问自己：只看我记下的信息，够不够决定接下来能怎么选、要付出多少代价？
如果够，就不需要重新查看前面的完整过程。这个特点通常叫作“无后效性”。如果不够，就需要补充信息，不能把不同情况混在一起。
3.2 动态规划中的几个常见术语
先理解例子，再记住下面几个名称即可。
名称 简单理解 本篇中的例子 重复子问题 同一个小问题被反复计算 不同递归分支都会计算“还剩 111 格时有多少种走法” 最优子结构 把最后一步固定以后，前面那一段也要尽量好 若最后一步从 i−1i-1i−1 走到 iii，就用到达 i−1i-1i−1 的最小花费，再加上这一步的费用 无后效性 信息记够以后，不用再翻看之前的完整过程 在前面的路线计数题中，知道剩余距离，就能确定后面有哪些走法
求方案数时，还要检查：所有合法方案有没有算全，同一种方案有没有被重复计算。 求最值时，要检查有没有漏掉可能更好的选择。
3.3 动态规划的解题步骤
写代码前，先回答五个问题：
1. 记什么？ 例如，dp[i]\mathrm{dp}[i]dp[i] 记的是到达位置 iii 的方案数，还是最小花费？
2. 从哪里来？ 到达当前位置之前，可能在哪些位置？这些情况怎样合起来？
3. 从哪里开始算？ 哪些答案一开始就知道？例如，起点的方案数或花费是多少？
4. 按什么顺序算？ 计算当前答案时，需要用到的结果是否已经算好？
5. 最后输出哪个数？ 答案是 dp[n]\mathrm{dp}[n]dp[n]，还是数组中最大的一个数？
估算时间时，可以先看需要计算多少个数组位置，再看每个位置要检查多少种来源。例如，有 nnn 个位置，每个只检查两个来源，时间通常是 O(n)O(n)O(n)；每个都要检查前面所有位置，时间通常是 O(n2)O(n^2)O(n2)。
4. 例题 L2：最小花费
题目
从位置 000 出发，到达位置 nnn。每次前进 111 或 222 个位置，不能超过 nnn。每次落在 iii 时支付 a[i]a[i]a[i]，起点不收费。求最小总花费。
范围： 1≤n≤1000001\le n\le 1000001≤n≤100000，0≤a[i]≤1090\le a[i]\le 10^{9}0≤a[i]≤109。
例如 a=[5,1,9,2,3]a=[5,1,9,2,3]a=[5,1,9,2,3]，最优路线为 0→2→4→50\to2\to4\to50→2→4→5，花费 1+2+3=61+2+3=61+2+3=6。
4.1 状态与转移
定义：
> dp[i]\mathrm{dp}[i]dp[i]：恰好到达位置 iii 的最小花费，包含 a[i]a[i]a[i]。
若最后来自 i−1i-1i−1，前面部分的花费应取 dp[i−1]\mathrm{dp}[i-1]dp[i−1]；若来自 i−2i-2i−2，则应取 dp[i−2]\mathrm{dp}[i-2]dp[i−2]。无论哪种，都要再支付 a[i]a[i]a[i]。
所以 i≥2i\ge 2i≥2 时：
dp[i]=min(dp[i−1],dp[i−2])+a[i]\mathrm{dp}[i]=\min (\mathrm{dp}[i-1],\mathrm{dp}[i-2])+a[i] dp[i]=min(dp[i−1],dp[i−2])+a[i]
边界：dp[0]=0\mathrm{dp}[0]=0dp[0]=0，dp[1]=a[1]\mathrm{dp}[1]=a[1]dp[1]=a[1]。
4.2 最优状态的保留
假设两条路线都到达位置 iii，第一条花费 777，第二条花费 101010。之后无论走哪些位置，两条路线都能采用相同走法，增加相同费用。因此第二条没有必要保留。
若题目增加“只能使用一次的折扣券”，且两条路线使用折扣券的情况不同，就不能仅比较当前花费；还要记录折扣券是否已用。
4.3 核心代码
调用方式： 数据已存入 nnn、a[1…n]a[1\ldots n]a[1…n]，答案为 minCost()。
iii 000 111 222 333 444 555 dp[i]\mathrm{dp}[i]dp[i] 000 555 111 101010 333 666
时间与空间均为 O(n)O(n)O(n)。最多累加约 101410^{14}1014，需要 long long。
想一想①： 如果不要求到达 nnn，只要求到达 nnn 或 n−1n-1n−1 中任意一个，答案位置应该怎样改变？
5. 例题 L3：非相邻元素的最大收益
题目
有 nnn 天，第 iii 天安排专题训练能获得 a[i]a[i]a[i] 点收益。不能连续两天安排，可以一天都不安排，求最大总收益。
范围： 1≤n≤1000001\le n\le 1000001≤n≤100000，−109≤a[i]≤109-10^{9}\le a[i]\le 10^{9}−109≤a[i]≤109。
例如 a=[5,1,2,10,6,2]a=[5,1,2,10,6,2]a=[5,1,2,10,6,2]，最大收益为 171717，可安排第 111、444、666 天。
5.1 前缀状态与转移
定义：
> dp[i]\mathrm{dp}[i]dp[i]：只考虑前 iii 天，能够获得的最大收益。
这里不要求第 iii 天必须安排。按第 iii 天是否安排分类：
* 不安排：最优收益为 dp[i−1]\mathrm{dp}[i-1]dp[i−1]。
* 安排：第 i−1i-1i−1 天不能安排，可在前 i−2i-2i−2 天中自由选择，再加 a[i]a[i]a[i]。
因此：
dp[i]=max(dp[i−1],dp[i−2]+a[i])\mathrm{dp}[i]=\max (\mathrm{dp}[i-1],\mathrm{dp}[i-2]+a[i]) dp[i]=max(dp[i−1],dp[i−2]+a[i])
dp[0]=0\mathrm{dp}[0]=0dp[0]=0；dp[1]=max(0,a[1])\mathrm{dp}[1]=\max (0,a[1])dp[1]=max(0,a[1])。
5.2 核心代码
调用方式： 数据已读入，答案为 bestSchedule()。
iii 000 111 222 333 444 555 666 dp[i]\mathrm{dp}[i]dp[i] 000 555 555 777 151515 151515 171717
时间与空间均为 O(n)O(n)O(n)。
若所有收益都为负数，什么都不安排得到 000。这个答案来自“允许空选”的条件；若要求至少安排一天，初始化和状态处理需要重新设计。
5.3 状态含义对比
L2 的 dp[i]\mathrm{dp}[i]dp[i] 表示“恰好到达 iii”；本题表示“只考虑前 iii 天”。虽然都写成一维数组，含义不同。
DP 数组的名字不能代替状态定义。写代码之前，应先把“必须”“可以”“恰好”“不超过”等限制说清楚。
想一想②： 如果安排一天后，接下来的两天都必须休息，转移应该怎样改？
6. 例题 L4：最大连续子段和
题目
给出 nnn 个整数，必须选择一个非空连续区间，求区间元素和的最大值。
范围： 1≤n≤1000001\le n\le 1000001≤n≤100000，−109≤a[i]≤109-10^{9}\le a[i]\le 10^{9}−109≤a[i]≤109。
例如 a=[4,−6,3,5,−2,4,−8,2]a=[4,-6,3,5,-2,4,-8,2]a=[4,−6,3,5,−2,4,−8,2]，答案为 101010，对应连续区间 [3,6][3,6][3,6]，即 3+5−2+43+5-2+43+5−2+4。
6.1 以当前位置结尾的状态
定义：
> dp[i]\mathrm{dp}[i]dp[i]：必须以第 iii 个元素结尾的非空连续区间，其最大元素和。
以 iii 结尾的连续区间只有两类：
1. 只有 a[i]a[i]a[i]。
2. 长度至少为 222，前一段必须以 i−1i-1i−1 结尾，再接 a[i]a[i]a[i]。
所以：
dp[i]=max(a[i],dp[i−1]+a[i])\mathrm{dp}[i]=\max (a[i],\mathrm{dp}[i-1]+a[i]) dp[i]=max(a[i],dp[i−1]+a[i])
dp[1]=a[1]\mathrm{dp}[1]=a[1]dp[1]=a[1]。答案是所有 dp[i]\mathrm{dp}[i]dp[i] 的最大值，而不是固定输出 dp[n]\mathrm{dp}[n]dp[n]。
6.2 核心代码
调用方式： 数据已读入，答案为 maxSubarray()。
iii 111 222 333 444 555 666 777 888 a[i]a[i]a[i] 444 −6-6−6 333 555 −2-2−2 444 −8-8−8 222 dp[i]\mathrm{dp}[i]dp[i] 444 −2-2−2 333 888 666 101010 222 444
时间与空间均为 O(n)O(n)O(n)。
如果数组为 [−5,−2,−7][-5,-2,-7][−5,−2,−7]，答案是 −2-2−2。把 ans\mathrm{ans}ans 初始化为 000 会错误地允许选择空区间。
6.3 连续区间与任意选取的区别
因为题目要求连续。正数之间夹着的负数，若位于所选区间内部，就不能跳过。L3 允许跳过若干天；本题不允许任意跳过区间内部元素。
想一想③： “最大连续区间和”与“最大子序列和”是否一定相同？用最小例子说明。
7. 例题 L5：最长上升子序列（LIS）
题目
给出 nnn 个整数，删除若干个，保留其余元素的相对顺序，使留下的序列严格递增，求最多能保留多少个。
范围： 1≤n≤20001\le n\le 20001≤n≤2000，−109≤a[i]≤109-10^{9}\le a[i]\le 10^{9}−109≤a[i]≤109。
例如 a=[4,2,3,1,5,4,6]a=[4,2,3,1,5,4,6]a=[4,2,3,1,5,4,6]，答案为 444，可以保留 222、333、555、666，或者 222、333、444、666。
7.1 子序列与状态设计
子序列要求保留原先后顺序，不要求连续；不能先对原数组排序，否则问题被改变。
定义：
> dp[i]\mathrm{dp}[i]dp[i]：必须以 a[i]a[i]a[i] 结尾的最长严格上升子序列长度。
若前一项选择 a[j]a[j]a[j]，需要同时满足：
* j<ij<ij<i，保证原先后顺序。
* a[j]<a[i]a[j]<a[i]a[j]<a[i]，保证严格递增。
每个合法前驱都给出候选值 dp[j]+1\mathrm{dp}[j]+1dp[j]+1。
7.2 转移与初始化
单独保留 a[i]a[i]a[i] 就是一条长度为 111 的上升子序列。因此先令 dp[i]=1\mathrm{dp}[i]=1dp[i]=1，再枚举合法 jjj：
dp[i]=max(dp[i],dp[j]+1)\mathrm{dp}[i]=\max (\mathrm{dp}[i],\mathrm{dp}[j]+1) dp[i]=max(dp[i],dp[j]+1)
最终答案为 max(dp[1],…,dp[n])\max (\mathrm{dp}[1],\ldots ,\mathrm{dp}[n])max(dp[1],…,dp[n])。
7.3 核心代码
调用方式： 数据已读入，答案为 longestIncreasing()。
iii 111 222 333 444 555 666 777 a[i]a[i]a[i] 444 222 333 111 555 444 666 dp[i]\mathrm{dp}[i]dp[i] 111 111 222 111 333 333 444
共有 nnn 个状态，每个最多枚举 O(n)O(n)O(n) 个前驱，时间 O(n2)O(n^{2})O(n2)，空间 O(n)O(n)O(n)。这也是线性 DP，“线性”不意味着转移必须是 O(1)O(1)O(1)。
7.4 前缀状态与结尾状态的区别
对 LIS 而言，仅保存“前 iii 项的最长长度”，却不记录其结尾数值，就很难判断能否接上新元素。
例如两个长度都为 222 的子序列：
* 222、333。
* 222、100100100。
接下来遇到 444，第一个可以连接，第二个不行。长度相同不代表后续条件相同，因此本例把结尾位置记进状态。
更高效的 O(nlogn)O(n \log n)O(nlogn) 做法需要另一种状态含义和二分维护，不属于本次基础实现；先把 O(n2)O(n^{2})O(n2) 的状态设计理解透彻。
7.5 严格上升与不下降
如果题目改成最长不下降子序列，应把比较条件改为 a[j]≤a[i]a[j]\le a[i]a[j]≤a[i]。例如 [2,2,2][2,2,2][2,2,2]：
* 严格上升答案为 111。
* 不下降答案为 333。
想一想④： 对 [1,2,3,0][1,2,3,0][1,2,3,0]，为什么最终答案不能直接取 dp[4]\mathrm{dp}[4]dp[4]？
8. 例题 L6：二维状态的线性 DP
题目
连续 nnn 天，每天必须选择活动 AAA 或活动 BBB。第 iii 天选择 AAA 得到 a[i]a[i]a[i] 收益，选择 BBB 得到 b[i]b[i]b[i] 收益。不能连续两天都选择 AAA，BBB 可以连续选择。求最大总收益。
范围： 1≤n≤1000001\le n\le 1000001≤n≤100000，−109≤a[i],b[i]≤109-10^{9}\le a[i],b[i]\le 10^{9}−109≤a[i],b[i]≤109。
例如 n=3n=3n=3：
* a=[6,8,4]a=[6,8,4]a=[6,8,4]。
* b=[2,3,5]b=[2,3,5]b=[2,3,5]。
选择 BBB、AAA、BBB，收益 2+8+5=152+8+5=152+8+5=15，是最大值。
8.1 状态维度的设计
在前 iii 天结束时，一个方案最后选择 AAA，另一个最后选择 BBB。即使当前收益相同，第二天可选项也不同：
* 以 AAA 结束，下一天不能选 AAA。
* 以 BBB 结束，下一天两种都能选。
因此要增加一个小状态，记录今天选了什么。
8.2 状态定义与转移
定义：
* dp[i][0]\mathrm{dp}[i][0]dp[i][0]：前 iii 天已处理，第 iii 天选择 BBB 的最大收益。
* dp[i][1]\mathrm{dp}[i][1]dp[i][1]：前 iii 天已处理，第 iii 天选择 AAA 的最大收益。
转移：
* 今天 BBB：昨天两种结尾都能来，dp[i][0]=max(dp[i−1][0],dp[i−1][1])+b[i]\mathrm{dp}[i][0]=\max (\mathrm{dp}[i-1][0],\mathrm{dp}[i-1][1])+b[i]dp[i][0]=max(dp[i−1][0],dp[i−1][1])+b[i]。
* 今天 AAA：昨天只能 BBB，dp[i][1]=dp[i−1][0]+a[i]\mathrm{dp}[i][1]=\mathrm{dp}[i-1][0]+a[i]dp[i][1]=dp[i−1][0]+a[i]。
第一天直接初始化：dp[1][0]=b[1]\mathrm{dp}[1][0]=b[1]dp[1][0]=b[1]，dp[1][1]=a[1]\mathrm{dp}[1][1]=a[1]dp[1][1]=a[1]。
8.3 核心代码
调用方式： 数据已读入，答案为 bestActivities()。
时间 O(n)O(n)O(n)，空间 O(n)O(n)O(n)。因为每天必须选一项，即使所有收益为负，也不能把答案改成 000。
这个例子说明：增加状态维度，是为了保存影响未来选择的信息。 不要因为担心二维数组，就强行删除必要状态。
9. 例题 L7：字符串划分计数
题目
给出一个由数字 000 到 999 组成的非空字符串，把它划分成若干个连续的段，要求：
* 每段长度为 111 或 222。
* 每段表示的整数在 111 到 262626 之间。
* 不能有前导零，例如 01、06 不合法，10、20 合法。
求不同的划分方案数，对 100000000710000000071000000007 取模。只要分段位置不同，就视为不同方案。
范围： 字符串长度 nnn 满足 1≤n≤1000001\le n\le 1000001≤n≤100000。
例如字符串 1210 有两种划分：
不能划成 1 | 21 | 0，因为 000 不是合法的一段；也不能把 121 作为一段，因为长度和数值都不符合要求。
本题把计数作为独立的线性 DP 模型来分析。与前面的最值题相比，核心任务是：把所有方案分成互不重叠的类别，再把各类数量相加。
9.1 前缀计数状态
定义：
> dp[i]\mathrm{dp}[i]dp[i]：字符串前 iii 个字符的合法划分方案数。
处理到第 iii 个字符时，不需要保留前面每一种划分的完整过程。只要前 iii 个字符已经合法划分，接下来能怎样添加新段，与此前具体在哪些位置分段无关。
这里保存的是方案数量，不是最大段数、最小段数或某一种具体划分。
9.2 按最后一段分类
前 iii 个字符的最后一段只能有两种长度。
第一类：最后一段只有 111 个字符。
若 s[i]s[i]s[i] 是 111 到 999，这一位可单独成段。把它接在前 i−1i-1i−1 个字符的每一种合法划分后面，贡献 dp[i−1]\mathrm{dp}[i-1]dp[i−1] 种方案。
若 s[i]s[i]s[i] 是 000，则不允许这一类转移。
第二类：最后一段有 222 个字符。
当 i≥2i\ge 2i≥2，把 s[i−1]s[i-1]s[i−1]、s[i]s[i]s[i] 组成两位数 xxx。如果 10≤x≤2610\le x\le 2610≤x≤26，就能把这两位接在前 i−2i-2i−2 个字符的每一种合法划分后面，贡献 dp[i−2]\mathrm{dp}[i-2]dp[i−2] 种方案。
x≥10x\ge 10x≥10 同时排除了前导零的情况。
因此，先令 dp[i]=0\mathrm{dp}[i]=0dp[i]=0，再把满足条件的来源累加：
* 单字符段合法：dp[i]+=dp[i−1]\mathrm{dp}[i]+=\mathrm{dp}[i-1]dp[i]+=dp[i−1]。
* 双字符段合法：dp[i]+=dp[i−2]\mathrm{dp}[i]+=\mathrm{dp}[i-2]dp[i]+=dp[i−2]。
每次累加后按要求取模。
9.3 分类的完整性与去重
任何合法划分的最后一段，要么长度为 111，要么长度为 222，因此没有遗漏。
这两类方案的最后一个分段位置不同，不能是同一种完整划分。对于固定的最后一段，删除它能唯一得到对应前缀的一种划分；反过来添加这一段，也能唯一恢复原方案。因此各类内部也没有重复。
这就是此处使用加法的依据。计数转移不能只看“有几个来源”，还要证明来源之间不重复，并且每次转移与新方案一一对应。
9.4 空前缀的初始化
令 dp[0]=1\mathrm{dp}[0]=1dp[0]=1，表示空字符串有一种划分方式：不划分任何段。
这一个空方案是构造第一个合法段的起点。例如字符串为 7 时，可以在空前缀后添加段 777，因此 dp[1]\mathrm{dp}[1]dp[1] 从 dp[0]\mathrm{dp}[0]dp[0] 得到 111。
若 dp[0]=0\mathrm{dp}[0]=0dp[0]=0，后面所有状态就都无法产生方案。这里的 111 不是额外增加一种最终答案，而是计数递推的初始条件。
没有合法划分的前缀，计数为 000；取模后的值为 000 也可能来自实际方案数为模数的倍数，不能仅凭取模结果判断是否存在方案。
9.5 核心代码
调用方式： 字符串已经存入 s[1…n]s[1\ldots n]s[1…n]，答案为 countSplits()。输入保证每个字符都是十进制数字。
9.6 手算与边界检查
对字符串 1210：
iii 当前前缀 最后一段长 111 的贡献 最后一段长 222 的贡献 dp[i]\mathrm{dp}[i]dp[i] 000 空 — — 111 111 111 dp[0]=1\mathrm{dp}[0]=1dp[0]=1 不存在两位段 111 222 121212 dp[1]=1\mathrm{dp}[1]=1dp[1]=1 121212 合法，dp[0]=1\mathrm{dp}[0]=1dp[0]=1 222 333 121121121 dp[2]=2\mathrm{dp}[2]=2dp[2]=2 212121 合法，dp[1]=1\mathrm{dp}[1]=1dp[1]=1
333 444 121012101210 000 不能单独成段 101010 合法，dp[2]=2\mathrm{dp}[2]=2dp[2]=2 222
注意，前缀 121 的方案数为 333，但增加一个字符后，方案数可能变小：其中一些前缀划分不能直接追加 000，需要把末尾重新划为 101010。
建议再检查：
字符串 答案 检查重点 0 000 单个 000 不合法 10 111 000 可以出现在合法的两位段中 01 000 不能忽略前导零 27 111 只能划成 222、777 30 000 303030 不合法，000 也不能独立 121 333 两类来源同时贡献
共有 n+1n+1n+1 个状态，每个状态检查至多两个来源，时间 O(n)O(n)O(n)，空间 O(n)O(n)O(n)。答案数量可能很大，必须在递推过程中取模。
想一想⑤： 计数题的 dp[0]=1\mathrm{dp}[0]=1dp[0]=1 与最值题的 dp[0]=0\mathrm{dp}[0]=0dp[0]=0，分别表示什么？本题为什么不能用 max\maxmax 合并两个来源？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 例题 L8：最长公共子序列（LCS）
题目
给出两个大写字母字符串 AAA、BBB。求一个尽可能长的字符串，它既是 AAA 的子序列，也是 BBB 的子序列。
范围： 1≤∣A∣,∣B∣≤10001\le \lvert A\rvert,\lvert B\rvert\le 10001≤∣A∣,∣B∣≤1000。
例如 A=ABCDA=\texttt{ABCD}A=ABCD，B=BACDB=\texttt{BACD}B=BACD，答案为 333；ACD、BCD 都是合法的最长公共子序列。
本节对应课纲中的 LCS 与基础二维状态设计，可在前面模型稳定后学习。
10.1 双序列前缀状态
定义：
> dp[i][j]\mathrm{dp}[i][j]dp[i][j]：AAA 的前 iii 个字符与 BBB 的前 jjj 个字符，最长公共子序列的长度。
当 i=0i=0i=0 或 j=0j=0j=0，一边为空，只能得到空子序列，长度为 000。
比较两边末尾：
* 若 A[i]=B[j]A[i]=B[j]A[i]=B[j]，可以把这对相同字符接在两个较短前缀的公共子序列后，得到 dp[i−1][j−1]+1\mathrm{dp}[i-1][j-1]+1dp[i−1][j−1]+1。
* 若 A[i]≠B[j]A[i]\ne B[j]A[i]=B[j]，末尾不能相互匹配，至少舍去一边末尾，取 max(dp[i−1][j],dp[i][j−1])\max (\mathrm{dp}[i-1][j],\mathrm{dp}[i][j-1])max(dp[i−1][j],dp[i][j−1])。
相等时取对角线加 111，并不是说所有最优方案都必须使用这两个具体位置；而是该长度一定能够达到，其他合法方案也不会超过它。若一个方案匹配了末尾字符，去掉最后匹配对后，剩余长度至多为较短前缀的 LCS；若它没有使用任一末尾位置，本就属于更短前缀。
10.2 核心代码
调用方式： AAA、BBB 已存入 a[1…n]a[1\ldots n]a[1…n]、b[1…m]b[1\ldots m]b[1…m]，答案为 longestCommon()。
每个状态检查常数个来源，共 O(nm)O(nm)O(nm) 个状态，时间与空间均为 O(nm)O(nm)O(nm)。
公共子序列不要求连续；公共子串要求连续，是另一个模型。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三章 动态规划方法总结
11. 常见模型与状态对照
模型 状态含义 为什么这样定义 答案位置 L1 路线计数 到达位置 iii 的方案数 便于按最后一步分类 dp[n]\mathrm{dp}[n]dp[n] L2 最小花费 恰好到达 iii 的最小花费 后续选择只由位置决定 dp[n]\mathrm{dp}[n]dp[n] L3 非相邻选择 前 iii 天的最大收益 按第 iii 天是否选择分类 dp[n]\mathrm{dp}[n]dp[n] L4 最大连续和 必须以 iii 结尾的最大连续和 连续区间必须从 i−1i-1i−1 延伸或重新开始 maxdp[i]\max \mathrm{dp}[i]maxdp[i] L5 LIS 必须以
a[i]a[i]a[i] 结尾的最优长度 下一个元素能否连接取决于结尾 maxdp[i]\max \mathrm{dp}[i]maxdp[i] L6 每日两类活动 前 iii 天、结尾类型 ttt 的最大收益 结尾类型影响下一天可选项 maxdp[n][t]\max \mathrm{dp}[n][t]maxdp[n][t] L7 字符串划分计数 前 iii 个字符的合法划分方案数 按最后一段的长度分类并求和 dp[n]\mathrm{dp}[n]dp[n] L8 LCS 两个前缀的 LCS 长度 需要同时记录两串处理到哪里 dp[n][m]\mathrm{dp}[n][m]dp[n][m]
看到一道新题时，先想“状态需要记录什么”，再想采用哪一种数组。不要反过来先决定开 dp[n]\mathrm{dp}[n]dp[n]，然后勉强给它找含义。
12. 初始化与不可达状态
情况 应该怎样理解 空对象的方案数 有时是 111，因为“什么都不做”是一种合法方案 必须选非空区间 用真实元素初始化，不能让空区间参与最优值 允许什么都不选 000 可能是一个合法候选答案 状态根本无法到达 不能伪装成“代价 000”或“收益 000” 第一阶段直接确定 单独初始化，后面再套统一转移
求最小值的不可达状态常用正无穷，求最大值的不可达状态常用负无穷；使用哨兵值时要保证它不与真实答案混淆，并避免在不可达状态上直接加减导致溢出。
