基础线性动态规划

深圳信奥中心-禹云龙

2026-10-31 01:47:34

发布于：广东

29阅读

0回复

0点赞

阅读导航

第一章：动态规划入门与记忆化搜索，例题 L1。
第二章：递推与基础概念，例题 L2—L8。
第三章：状态对照、初始化、计算顺序、空间优化与方案还原。

第一章　动态规划入门与记忆化搜索

动态规划会把重复出现、后续条件相同的子问题整理成状态，并保存它们的答案。本章先从已经熟悉的递归搜索出发，观察重复计算，再用记忆化保存结果；记忆化搜索在本篇属于动态规划的实现方式。

1. 例题 L1：路线方案计数

题目

一条路线从位置 $0$ 到位置 $n$ 。每次只能前进 $1$ 格或 $3$ 格，不能超过终点。不同移动顺序算不同方案，求到达 $n$ 的方案数，对 $1000000007$ 取模。

普通递归演示： $0\le n\le 30$ 。
记忆化演示： $0\le n\le 1000$ 。
递推实现： $0\le n\le 100000$ 。

$n=5$ 时答案为 $4$ ：

1+1+1+1+1
1+1+3
1+3+1
3+1+1

$n=0$ 时，不移动也算 $1$ 种方案。

1.1 递归状态与转移

设 $\mathrm{dfs}(r)$ 返回：还剩 $r$ 格时，有多少种走法。

第一步如果走 $1$ 格，后续有 $\mathrm{dfs}(r-1)$ 种；如果走 $3$ 格，后续有 $\mathrm{dfs}(r-3)$ 种。两类方案第一步不同，互不重叠，所以可以相加。

边界为：

$r=0$ ：恰好完成，返回 $1$ 。
$r<0$ ：越过终点，返回 $0$ 。

1.2 普通递归的核心代码

const int MOD=1000000007;
int dfs(int r){
	if(r==0)return 1;
	if(r<0)return 0;
	return (dfs(r-1)+dfs(r-3))%MOD;
}

调用方式： 使用小范围 $n$ ，计算 $\mathrm{dfs}(n)$ 。

1.3 重复子问题

取 $n=4$ ，把普通递归展开成决策树。为便于阅读，只画剩余距离非负的合法分支；越过终点的分支返回 $0$ ，不在图中展开。

右侧的“剩余 $1$ 格”来自第一步走 $3$ 格；左侧的“剩余 $1$ 格”来自连续走了三次 $1$ 格。它们处在不同决策路径下，但后续问题相同：还剩 $1$ 格，只有走 $1$ 格这一种完成方式。

普通 DFS 会分别展开这两个节点。记忆化则让第一次计算得到的 $\mathrm{dfs}(1)=1$ 被保存，第二次需要时直接取用。

这里要区分两件事：前面已经走出的过程不同，完整方案仍然不同；需要复用的是后续子问题的计算结果。如果题目只问总数量，就不必重复展开完全相同的后续过程。

1.4 记忆化核心代码

const int N=1010,MOD=1000000007;
int f[N];
bool done[N];
int dfs(int r){
	if(r==0)return 1;
	if(r<0)return 0;
	if(done[r])return f[r];
	f[r]=(dfs(r-1)+dfs(r-3))%MOD;
	done[r]=true;
	return f[r];
}

调用方式： $\mathrm{done}$ 初始为全 $\mathrm{false}$ ，答案为 $\mathrm{dfs}(n)$ 。若在同一程序中处理新测试，需重新初始化对应记忆化数据。

这里用 $\mathrm{done}$ 区分“没算过”和“答案恰好为 $0$ ”。即使方案数取模后为 $0$ ，也不应该当作没算过而反复展开。

每个非负 $r$ 状态只需要真正计算一次，时间 $O(n)$ ，数组与递归栈空间 $O(n)$ 。

1.5 记忆化结果的使用

$\mathrm{dfs}(r)$ 返回的是这个后续问题的方案数。如果不同前缀都来到同一个 $r$ ，它们都要把该方案数加入各自结果，只是无需重新展开计算。

若只是发现 $r$ 见过便直接返回 $0$ ，就可能把不同前缀能够形成的方案一起删掉。

决策树中的多个 $F(1)$ 节点在这里共用一个计算结果； $F(0)$ 也只保留一个状态。它不再是一棵每个节点只有一个父节点的树，而是一张可以被不同状态共同依赖的图。

在本题中，每次依赖的剩余距离都会减小，不会绕回原状态，因此这张图没有环。我们既可以沿依赖递归求解并保存答案，也可以先求小状态，再依次求大状态。

例如 $F(0)=1$ 、 $F(1)=1$ 、 $F(2)=1$ 、 $F(3)=2$ ，所以 $F(4)=F(3)+F(1)=3$ 。三种完整走法是 $1+1+1+1$ 、 $1+3$ 、 $3+1$ ；复用 $F(1)$ 不会把后两种走法合成同一种方案。

1.6 记忆化的适用条件

以“同一条路线不能重复经过格子”的迷宫路径计数为例：

两条路线到达相同格子。
但一条路线用过左边的格子，另一条用过上边的格子。
接下来可选路径可能不同。

仅用位置 $(x,y)$ 不足以确定答案，不能直接设置 $f[x][y]$ 记忆化。

另外，本例 $r$ 持续减小，没有循环依赖。一般有环状态不能简单标记为“已算过”就读取答案，否则可能读到尚未计算完成的值。递归深度过大还可能导致栈溢出；记忆化不等于适合无限增大 $n$ 。

第二章　基础线性动态规划

2. 动态规划的递推实现

仍然看 L1。既然剩余 $r$ 的答案只依赖更小的数，就可以直接先算小的，再算大的。

对照上一节的状态依赖图，这个顺序就是先得到 $F(0)$ ，再求 $F(1)$ 、 $F(2)$ 、 $F(3)$ ……每次需要的较小状态都已经完成。这样就把“沿决策树向下尝试”的过程，转成了“按依赖顺序计算状态”。

也可以换一个等价角度，定义：

$\mathrm{dp}[i]$ ：从位置 $0$ 到达位置 $i$ 的方案数。

按最后一步分类：

最后走 $1$ 格：来自 $i-1$ 。
最后走 $3$ 格：来自 $i-3$ 。

于是：

$\mathrm{dp}[i]=\mathrm{dp}[i-1]+\mathrm{dp}[i-3]$

不存在的负下标来源按 $0$ 处理。

2.1 递推核心代码

const int N=100010,MOD=1000000007;
int n,dp[N];
int countWays(){
	dp[0]=1;
	for(int i=1;i<=n;i++){
		dp[i]=dp[i-1];
		if(i>=3)dp[i]=(dp[i]+dp[i-3])%MOD;
	}
	return dp[n];
}

调用方式： 读入 $n$ 后，答案为 countWays()。

$i$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$\mathrm{dp}[i]$	$1$	$1$	$1$	$2$	$3$	$4$	$6$

时间 $O(n)$ ，空间 $O(n)$ 。

记忆化和递推不是两套不同的数学原理。两者复用了子问题答案，区别主要在计算的组织方式：前者沿着依赖递归求解，后者直接安排好顺序。

3. 线性动态规划的基本概念

前面的路线计数题中，我们没有把每一种完整走法都重新走一遍，而是记录“到达每个位置有多少种走法”，再利用已经算出的结果，计算其他位置的答案。

动态规划的一个重要做法，就是先解决一些小问题，把答案记下来，再用它们解决更大的问题。

本篇学习的线性动态规划，常常处理这样的问题：

一条路线：考虑到达第 $1$ 个、第 $2$ 个位置时的答案。
连续几天的安排：考虑前 $1$ 天、前 $2$ 天的答案。
一串数字：考虑前几个数字，或者以某个数字结尾时的答案。

这些问题都有一定的先后顺序。写成递推时，要先算出当前需要用到的结果，再继续计算。

这里的“线性”不表示程序只能写一层循环，也不表示只能用一维数组。有时计算一个位置的答案，需要比较前面很多位置，时间可能是 $O(n^2)$ ；有时还要多记一项信息，例如“到了第几天、今天选了哪种活动”，就可能使用二维数组。后面的例题会逐步说明。

3.1 状态设计

“状态”这个词看起来抽象，可以先把它理解为：我们现在要解决的是哪一个小问题？

例如，在路线计数题中，可以写：

$\mathrm{dp}[i]$ ：从起点走到位置 $i$ ，一共有多少种走法。

这里，下标 $i$ 告诉我们“走到哪里”；数组中存放的数，告诉我们“有多少种走法”。所以，写 $\mathrm{dp}[i]$ 之前，要先说清楚这两件事。

那么，要不要把前面具体怎么走都记下来呢？这要看题目的要求。

如果求方案数，就要把不同的合法走法都计入。 只要后面允许的走法只由当前位置决定，就可以先记下到达这里的方案数，继续计算，不必逐条保存完整路线。

如果求最小花费，有些较差的走法就不必保留。 例如，每次只能前进 $1$ 或 $2$ 个位置，费用只由落在哪个位置决定。两条路线都到达位置 $5$ ，一条已经花了 $7$ 元，另一条花了 $10$ 元。接下来，两条路线能采用相同的走法，支付相同的费用，因此只保留花费 $7$ 元的结果就够了。

但如果题目中还有一张只能使用一次的优惠券，两条路线到达同一位置时，一条已经用过，另一条还没用过，后面的花费就可能不同。此时除了位置，还要记录“优惠券是否已经使用”。

因此，设计状态时可以问自己：只看我记下的信息，够不够决定接下来能怎么选、要付出多少代价？

如果够，就不需要重新查看前面的完整过程。这个特点通常叫作“无后效性”。如果不够，就需要补充信息，不能把不同情况混在一起。

3.2 动态规划中的几个常见术语

先理解例子，再记住下面几个名称即可。

名称	简单理解	本篇中的例子
重复子问题	同一个小问题被反复计算	不同递归分支都会计算“还剩 $1$ 格时有多少种走法”
最优子结构	把最后一步固定以后，前面那一段也要尽量好	若最后一步从 $i-1$ 走到 $i$ ，就用到达 $i-1$ 的最小花费，再加上这一步的费用
无后效性	信息记够以后，不用再翻看之前的完整过程	在前面的路线计数题中，知道剩余距离，就能确定后面有哪些走法

求方案数时，还要检查：所有合法方案有没有算全，同一种方案有没有被重复计算。 求最值时，要检查有没有漏掉可能更好的选择。

3.3 动态规划的解题步骤

写代码前，先回答五个问题：

记什么？ 例如， $\mathrm{dp}[i]$ 记的是到达位置 $i$ 的方案数，还是最小花费？
从哪里来？ 到达当前位置之前，可能在哪些位置？这些情况怎样合起来？
从哪里开始算？ 哪些答案一开始就知道？例如，起点的方案数或花费是多少？
按什么顺序算？ 计算当前答案时，需要用到的结果是否已经算好？
最后输出哪个数？ 答案是 $\mathrm{dp}[n]$ ，还是数组中最大的一个数？

估算时间时，可以先看需要计算多少个数组位置，再看每个位置要检查多少种来源。例如，有 $n$ 个位置，每个只检查两个来源，时间通常是 $O(n)$ ；每个都要检查前面所有位置，时间通常是 $O(n^2)$ 。

4. 例题 L2：最小花费

题目

从位置 $0$ 出发，到达位置 $n$ 。每次前进 $1$ 或 $2$ 个位置，不能超过 $n$ 。每次落在 $i$ 时支付 $a[i]$ ，起点不收费。求最小总花费。

范围： $1\le n\le 100000$ ， $0\le a[i]\le 10^{9}$ 。

例如 $a=[5,1,9,2,3]$ ，最优路线为 $0\to2\to4\to5$ ，花费 $1+2+3=6$ 。

4.1 状态与转移

定义：

$\mathrm{dp}[i]$ ：恰好到达位置 $i$ 的最小花费，包含 $a[i]$ 。

若最后来自 $i-1$ ，前面部分的花费应取 $\mathrm{dp}[i-1]$ ；若来自 $i-2$ ，则应取 $\mathrm{dp}[i-2]$ 。无论哪种，都要再支付 $a[i]$ 。

所以 $i\ge 2$ 时：

$\mathrm{dp}[i]=\min (\mathrm{dp}[i-1],\mathrm{dp}[i-2])+a[i]$

边界： $\mathrm{dp}[0]=0$ ， $\mathrm{dp}[1]=a[1]$ 。

4.2 最优状态的保留

假设两条路线都到达位置 $i$ ，第一条花费 $7$ ，第二条花费 $10$ 。之后无论走哪些位置，两条路线都能采用相同走法，增加相同费用。因此第二条没有必要保留。

若题目增加“只能使用一次的折扣券”，且两条路线使用折扣券的情况不同，就不能仅比较当前花费；还要记录折扣券是否已用。

4.3 核心代码

const int N=100010;
int n;
long long a[N],dp[N];
long long minCost(){
	dp[0]=0;
	dp[1]=a[1];
	for(int i=2;i<=n;i++)dp[i]=min(dp[i-1],dp[i-2])+a[i];
	return dp[n];
}

调用方式： 数据已存入 $n$ 、 $a[1\ldots n]$ ，答案为 minCost()。

$i$	$0$	$1$	$2$	$3$	$4$	$5$
$\mathrm{dp}[i]$	$0$	$5$	$1$	$10$	$3$	$6$

时间与空间均为 $O(n)$ 。最多累加约 $10^{14}$ ，需要 long long。

想一想①： 如果不要求到达 $n$ ，只要求到达 $n$ 或 $n-1$ 中任意一个，答案位置应该怎样改变？

5. 例题 L3：非相邻元素的最大收益

题目

有 $n$ 天，第 $i$ 天安排专题训练能获得 $a[i]$ 点收益。不能连续两天安排，可以一天都不安排，求最大总收益。

范围： $1\le n\le 100000$ ， $-10^{9}\le a[i]\le 10^{9}$ 。

例如 $a=[5,1,2,10,6,2]$ ，最大收益为 $17$ ，可安排第 $1$ 、 $4$ 、 $6$ 天。

5.1 前缀状态与转移

定义：

$\mathrm{dp}[i]$ ：只考虑前 $i$ 天，能够获得的最大收益。

这里不要求第 $i$ 天必须安排。按第 $i$ 天是否安排分类：

不安排：最优收益为 $\mathrm{dp}[i-1]$ 。
安排：第 $i-1$ 天不能安排，可在前 $i-2$ 天中自由选择，再加 $a[i]$ 。

因此：

$\mathrm{dp}[i]=\max (\mathrm{dp}[i-1],\mathrm{dp}[i-2]+a[i])$

$\mathrm{dp}[0]=0$ ； $\mathrm{dp}[1]=\max (0,a[1])$ 。

5.2 核心代码

const int N=100010;
int n;
long long a[N],dp[N];
long long bestSchedule(){
	dp[0]=0;
	dp[1]=max(0LL,a[1]);
	for(int i=2;i<=n;i++)dp[i]=max(dp[i-1],dp[i-2]+a[i]);
	return dp[n];
}

调用方式： 数据已读入，答案为 bestSchedule()。

$i$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$\mathrm{dp}[i]$	$0$	$5$	$5$	$7$	$15$	$15$	$17$

时间与空间均为 $O(n)$ 。

若所有收益都为负数，什么都不安排得到 $0$ 。这个答案来自“允许空选”的条件；若要求至少安排一天，初始化和状态处理需要重新设计。

5.3 状态含义对比

L2 的 $\mathrm{dp}[i]$ 表示“恰好到达 $i$ ”；本题表示“只考虑前 $i$ 天”。虽然都写成一维数组，含义不同。

DP 数组的名字不能代替状态定义。写代码之前，应先把“必须”“可以”“恰好”“不超过”等限制说清楚。

想一想②： 如果安排一天后，接下来的两天都必须休息，转移应该怎样改？

6. 例题 L4：最大连续子段和

题目

给出 $n$ 个整数，必须选择一个非空连续区间，求区间元素和的最大值。

范围： $1\le n\le 100000$ ， $-10^{9}\le a[i]\le 10^{9}$ 。

例如 $a=[4,-6,3,5,-2,4,-8,2]$ ，答案为 $10$ ，对应连续区间 $[3,6]$ ，即 $3+5-2+4$ 。

6.1 以当前位置结尾的状态

定义：

$\mathrm{dp}[i]$ ：必须以第 $i$ 个元素结尾的非空连续区间，其最大元素和。

以 $i$ 结尾的连续区间只有两类：

只有 $a[i]$ 。
长度至少为 $2$ ，前一段必须以 $i-1$ 结尾，再接 $a[i]$ 。

所以：

$\mathrm{dp}[i]=\max (a[i],\mathrm{dp}[i-1]+a[i])$

$\mathrm{dp}[1]=a[1]$ 。答案是所有 $\mathrm{dp}[i]$ 的最大值，而不是固定输出 $\mathrm{dp}[n]$ 。

6.2 核心代码

const int N=100010;
int n;
long long a[N],dp[N];
long long maxSubarray(){
	dp[1]=a[1];
	long long ans=dp[1];
	for(int i=2;i<=n;i++){
		dp[i]=max(a[i],dp[i-1]+a[i]);
		ans=max(ans,dp[i]);
	}
	return ans;
}

调用方式： 数据已读入，答案为 maxSubarray()。

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$a[i]$	$4$	$-6$	$3$	$5$	$-2$	$4$	$-8$	$2$
$\mathrm{dp}[i]$	$4$	$-2$	$3$	$8$	$6$	$10$	$2$	$4$

时间与空间均为 $O(n)$ 。

如果数组为 $[-5,-2,-7]$ ，答案是 $-2$ 。把 $\mathrm{ans}$ 初始化为 $0$ 会错误地允许选择空区间。

6.3 连续区间与任意选取的区别

因为题目要求连续。正数之间夹着的负数，若位于所选区间内部，就不能跳过。L3 允许跳过若干天；本题不允许任意跳过区间内部元素。

想一想③： “最大连续区间和”与“最大子序列和”是否一定相同？用最小例子说明。

7. 例题 L5：最长上升子序列（LIS）

题目

给出 $n$ 个整数，删除若干个，保留其余元素的相对顺序，使留下的序列严格递增，求最多能保留多少个。

范围： $1\le n\le 2000$ ， $-10^{9}\le a[i]\le 10^{9}$ 。

例如 $a=[4,2,3,1,5,4,6]$ ，答案为 $4$ ，可以保留 $2$ 、 $3$ 、 $5$ 、 $6$ ，或者 $2$ 、 $3$ 、 $4$ 、 $6$ 。

7.1 子序列与状态设计

子序列要求保留原先后顺序，不要求连续；不能先对原数组排序，否则问题被改变。

定义：

$\mathrm{dp}[i]$ ：必须以 $a[i]$ 结尾的最长严格上升子序列长度。

若前一项选择 $a[j]$ ，需要同时满足：

$j<i$ ，保证原先后顺序。
$a[j]<a[i]$ ，保证严格递增。

每个合法前驱都给出候选值 $\mathrm{dp}[j]+1$ 。

7.2 转移与初始化

单独保留 $a[i]$ 就是一条长度为 $1$ 的上升子序列。因此先令 $\mathrm{dp}[i]=1$ ，再枚举合法 $j$ ：

$\mathrm{dp}[i]=\max (\mathrm{dp}[i],\mathrm{dp}[j]+1)$

最终答案为 $\max (\mathrm{dp}[1],\ldots ,\mathrm{dp}[n])$ 。

7.3 核心代码

const int N=2010;
int n,a[N],dp[N];
int longestIncreasing(){
	int ans=0;
	for(int i=1;i<=n;i++){
		dp[i]=1;
		for(int j=1;j<i;j++){
			if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
		}
		ans=max(ans,dp[i]);
	}
	return ans;
}

调用方式： 数据已读入，答案为 longestIncreasing()。

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$a[i]$	$4$	$2$	$3$	$1$	$5$	$4$	$6$
$\mathrm{dp}[i]$	$1$	$1$	$2$	$1$	$3$	$3$	$4$

共有 $n$ 个状态，每个最多枚举 $O(n)$ 个前驱，时间 $O(n^{2})$ ，空间 $O(n)$ 。这也是线性 DP，“线性”不意味着转移必须是 $O(1)$ 。

7.4 前缀状态与结尾状态的区别

对 LIS 而言，仅保存“前 $i$ 项的最长长度”，却不记录其结尾数值，就很难判断能否接上新元素。

例如两个长度都为 $2$ 的子序列：

$2$ 、 $3$ 。
$2$ 、 $100$ 。

接下来遇到 $4$ ，第一个可以连接，第二个不行。长度相同不代表后续条件相同，因此本例把结尾位置记进状态。

更高效的 $O(n \log n)$ 做法需要另一种状态含义和二分维护，不属于本次基础实现；先把 $O(n^{2})$ 的状态设计理解透彻。

7.5 严格上升与不下降

如果题目改成最长不下降子序列，应把比较条件改为 $a[j]\le a[i]$ 。例如 $[2,2,2]$ ：

严格上升答案为 $1$ 。
不下降答案为 $3$ 。

想一想④： 对 $[1,2,3,0]$ ，为什么最终答案不能直接取 $\mathrm{dp}[4]$ ？

8. 例题 L6：二维状态的线性 DP

题目

连续 $n$ 天，每天必须选择活动 $A$ 或活动 $B$ 。第 $i$ 天选择 $A$ 得到 $a[i]$ 收益，选择 $B$ 得到 $b[i]$ 收益。不能连续两天都选择 $A$ ， $B$ 可以连续选择。求最大总收益。

范围： $1\le n\le 100000$ ， $-10^{9}\le a[i],b[i]\le 10^{9}$ 。

例如 $n=3$ ：

$a=[6,8,4]$ 。
$b=[2,3,5]$ 。

选择 $B$ 、 $A$ 、 $B$ ，收益 $2+8+5=15$ ，是最大值。

8.1 状态维度的设计

在前 $i$ 天结束时，一个方案最后选择 $A$ ，另一个最后选择 $B$ 。即使当前收益相同，第二天可选项也不同：

以 $A$ 结束，下一天不能选 $A$ 。
以 $B$ 结束，下一天两种都能选。

因此要增加一个小状态，记录今天选了什么。

8.2 状态定义与转移

定义：

$\mathrm{dp}[i][0]$ ：前 $i$ 天已处理，第 $i$ 天选择 $B$ 的最大收益。
$\mathrm{dp}[i][1]$ ：前 $i$ 天已处理，第 $i$ 天选择 $A$ 的最大收益。

转移：

今天 $B$ ：昨天两种结尾都能来， $\mathrm{dp}[i][0]=\max (\mathrm{dp}[i-1][0],\mathrm{dp}[i-1][1])+b[i]$ 。
今天 $A$ ：昨天只能 $B$ ， $\mathrm{dp}[i][1]=\mathrm{dp}[i-1][0]+a[i]$ 。

第一天直接初始化： $\mathrm{dp}[1][0]=b[1]$ ， $\mathrm{dp}[1][1]=a[1]$ 。

8.3 核心代码

const int N=100010;
int n;
long long a[N],b[N],dp[N][2];
long long bestActivities(){
	dp[1][0]=b[1];
	dp[1][1]=a[1];
	for(int i=2;i<=n;i++){
		dp[i][0]=max(dp[i-1][0],dp[i-1][1])+b[i];
		dp[i][1]=dp[i-1][0]+a[i];
	}
	return max(dp[n][0],dp[n][1]);
}

调用方式： 数据已读入，答案为 bestActivities()。

时间 $O(n)$ ，空间 $O(n)$ 。因为每天必须选一项，即使所有收益为负，也不能把答案改成 $0$ 。

这个例子说明：增加状态维度，是为了保存影响未来选择的信息。 不要因为担心二维数组，就强行删除必要状态。

9. 例题 L7：字符串划分计数

题目

给出一个由数字 $0$ 到 $9$ 组成的非空字符串，把它划分成若干个连续的段，要求：

每段长度为 $1$ 或 $2$ 。
每段表示的整数在 $1$ 到 $26$ 之间。
不能有前导零，例如 01、06 不合法，10、20 合法。

求不同的划分方案数，对 $1000000007$ 取模。只要分段位置不同，就视为不同方案。

范围： 字符串长度 $n$ 满足 $1\le n\le 100000$ 。

例如字符串 1210 有两种划分：

1 | 2 | 10
12 | 10

不能划成 1 | 21 | 0，因为 $0$ 不是合法的一段；也不能把 121 作为一段，因为长度和数值都不符合要求。

本题把计数作为独立的线性 DP 模型来分析。与前面的最值题相比，核心任务是：把所有方案分成互不重叠的类别，再把各类数量相加。

9.1 前缀计数状态

定义：

$\mathrm{dp}[i]$ ：字符串前 $i$ 个字符的合法划分方案数。

处理到第 $i$ 个字符时，不需要保留前面每一种划分的完整过程。只要前 $i$ 个字符已经合法划分，接下来能怎样添加新段，与此前具体在哪些位置分段无关。

这里保存的是方案数量，不是最大段数、最小段数或某一种具体划分。

9.2 按最后一段分类

前 $i$ 个字符的最后一段只能有两种长度。

第一类：最后一段只有 $1$ 个字符。

若 $s[i]$ 是 $1$ 到 $9$ ，这一位可单独成段。把它接在前 $i-1$ 个字符的每一种合法划分后面，贡献 $\mathrm{dp}[i-1]$ 种方案。

若 $s[i]$ 是 $0$ ，则不允许这一类转移。

第二类：最后一段有 $2$ 个字符。

当 $i\ge 2$ ，把 $s[i-1]$ 、 $s[i]$ 组成两位数 $x$ 。如果 $10\le x\le 26$ ，就能把这两位接在前 $i-2$ 个字符的每一种合法划分后面，贡献 $\mathrm{dp}[i-2]$ 种方案。

$x\ge 10$ 同时排除了前导零的情况。

因此，先令 $\mathrm{dp}[i]=0$ ，再把满足条件的来源累加：

单字符段合法： $\mathrm{dp}[i]+=\mathrm{dp}[i-1]$ 。
双字符段合法： $\mathrm{dp}[i]+=\mathrm{dp}[i-2]$ 。

每次累加后按要求取模。

9.3 分类的完整性与去重

任何合法划分的最后一段，要么长度为 $1$ ，要么长度为 $2$ ，因此没有遗漏。

这两类方案的最后一个分段位置不同，不能是同一种完整划分。对于固定的最后一段，删除它能唯一得到对应前缀的一种划分；反过来添加这一段，也能唯一恢复原方案。因此各类内部也没有重复。

这就是此处使用加法的依据。计数转移不能只看“有几个来源”，还要证明来源之间不重复，并且每次转移与新方案一一对应。

9.4 空前缀的初始化

令 $\mathrm{dp}[0]=1$ ，表示空字符串有一种划分方式：不划分任何段。

这一个空方案是构造第一个合法段的起点。例如字符串为 7 时，可以在空前缀后添加段 $7$ ，因此 $\mathrm{dp}[1]$ 从 $\mathrm{dp}[0]$ 得到 $1$ 。

若 $\mathrm{dp}[0]=0$ ，后面所有状态就都无法产生方案。这里的 $1$ 不是额外增加一种最终答案，而是计数递推的初始条件。

没有合法划分的前缀，计数为 $0$ ；取模后的值为 $0$ 也可能来自实际方案数为模数的倍数，不能仅凭取模结果判断是否存在方案。

9.5 核心代码

const int N=100010,MOD=1000000007;
int n,dp[N];
char s[N];
int countSplits(){
	dp[0]=1;
	for(int i=1;i<=n;i++){
		dp[i]=0;
		if(s[i]!='0')dp[i]=dp[i-1];
		if(i>=2){
			int x=(s[i-1]-'0')*10+s[i]-'0';
			if(x>=10&&x<=26)dp[i]=(dp[i]+dp[i-2])%MOD;
		}
	}
	return dp[n];
}

调用方式： 字符串已经存入 $s[1\ldots n]$ ，答案为 countSplits()。输入保证每个字符都是十进制数字。

9.6 手算与边界检查

对字符串 1210：

$i$	当前前缀	最后一段长 $1$ 的贡献	最后一段长 $2$ 的贡献	$\mathrm{dp}[i]$
$0$	空	—	—	$1$
$1$	$1$	$\mathrm{dp}[0]=1$	不存在两位段	$1$
$2$	$12$	$\mathrm{dp}[1]=1$	$12$ 合法， $\mathrm{dp}[0]=1$	$2$
$3$	$121$	$\mathrm{dp}[2]=2$	$21$ 合法， $\mathrm{dp}[1]=1$	$3$
$4$	$1210$	$0$ 不能单独成段	$10$ 合法， $\mathrm{dp}[2]=2$	$2$

注意，前缀 121 的方案数为 $3$ ，但增加一个字符后，方案数可能变小：其中一些前缀划分不能直接追加 $0$ ，需要把末尾重新划为 $10$ 。

建议再检查：

字符串	答案	检查重点
`0`	$0$	单个 $0$ 不合法
`10`	$1$	$0$ 可以出现在合法的两位段中
`01`	$0$	不能忽略前导零
`27`	$1$	只能划成 $2$ 、 $7$
`30`	$0$	$30$ 不合法， $0$ 也不能独立
`121`	$3$	两类来源同时贡献

共有 $n+1$ 个状态，每个状态检查至多两个来源，时间 $O(n)$ ，空间 $O(n)$ 。答案数量可能很大，必须在递推过程中取模。

想一想⑤： 计数题的 $\mathrm{dp}[0]=1$ 与最值题的 $\mathrm{dp}[0]=0$ ，分别表示什么？本题为什么不能用 $\max$ 合并两个来源？

10. 例题 L8：最长公共子序列（LCS）

题目

给出两个大写字母字符串 $A$ 、 $B$ 。求一个尽可能长的字符串，它既是 $A$ 的子序列，也是 $B$ 的子序列。

范围： $1\le \lvert A\rvert,\lvert B\rvert\le 1000$ 。

例如 $A=\texttt{ABCD}$ ， $B=\texttt{BACD}$ ，答案为 $3$ ；ACD、BCD 都是合法的最长公共子序列。

本节对应课纲中的 LCS 与基础二维状态设计，可在前面模型稳定后学习。

10.1 双序列前缀状态

定义：

$\mathrm{dp}[i][j]$ ： $A$ 的前 $i$ 个字符与 $B$ 的前 $j$ 个字符，最长公共子序列的长度。

当 $i=0$ 或 $j=0$ ，一边为空，只能得到空子序列，长度为 $0$ 。

比较两边末尾：

若 $A[i]=B[j]$ ，可以把这对相同字符接在两个较短前缀的公共子序列后，得到 $\mathrm{dp}[i-1][j-1]+1$ 。
若 $A[i]\ne B[j]$ ，末尾不能相互匹配，至少舍去一边末尾，取 $\max (\mathrm{dp}[i-1][j],\mathrm{dp}[i][j-1])$ 。

相等时取对角线加 $1$ ，并不是说所有最优方案都必须使用这两个具体位置；而是该长度一定能够达到，其他合法方案也不会超过它。若一个方案匹配了末尾字符，去掉最后匹配对后，剩余长度至多为较短前缀的 LCS；若它没有使用任一末尾位置，本就属于更短前缀。

10.2 核心代码

const int N=1010;
int n,m,dp[N][N];
char a[N],b[N];
int longestCommon(){
	for(int i=0;i<=n;i++)dp[i][0]=0;
	for(int j=0;j<=m;j++)dp[0][j]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	return dp[n][m];
}

调用方式： $A$ 、 $B$ 已存入 $a[1\ldots n]$ 、 $b[1\ldots m]$ ，答案为 longestCommon()。

每个状态检查常数个来源，共 $O(nm)$ 个状态，时间与空间均为 $O(nm)$ 。

公共子序列不要求连续；公共子串要求连续，是另一个模型。

第三章　动态规划方法总结

11. 常见模型与状态对照

模型	状态含义	为什么这样定义	答案位置
L1 路线计数	到达位置 $i$ 的方案数	便于按最后一步分类	$\mathrm{dp}[n]$
L2 最小花费	恰好到达 $i$ 的最小花费	后续选择只由位置决定	$\mathrm{dp}[n]$
L3 非相邻选择	前 $i$ 天的最大收益	按第 $i$ 天是否选择分类	$\mathrm{dp}[n]$
L4 最大连续和	必须以 $i$ 结尾的最大连续和	连续区间必须从 $i-1$ 延伸或重新开始	$\max \mathrm{dp}[i]$
L5 LIS	必须以 $a[i]$ 结尾的最优长度	下一个元素能否连接取决于结尾	$\max \mathrm{dp}[i]$
L6 每日两类活动	前 $i$ 天、结尾类型 $t$ 的最大收益	结尾类型影响下一天可选项	$\max \mathrm{dp}[n][t]$
L7 字符串划分计数	前 $i$ 个字符的合法划分方案数	按最后一段的长度分类并求和	$\mathrm{dp}[n]$
L8 LCS	两个前缀的 LCS 长度	需要同时记录两串处理到哪里	$\mathrm{dp}[n][m]$

看到一道新题时，先想“状态需要记录什么”，再想采用哪一种数组。不要反过来先决定开 $\mathrm{dp}[n]$ ，然后勉强给它找含义。

12. 初始化与不可达状态

情况	应该怎样理解
空对象的方案数	有时是 $1$ ，因为“什么都不做”是一种合法方案
必须选非空区间	用真实元素初始化，不能让空区间参与最优值
允许什么都不选	$0$ 可能是一个合法候选答案
状态根本无法到达	不能伪装成“代价 $0$ ”或“收益 $0$ ”
第一阶段直接确定	单独初始化，后面再套统一转移

求最小值的不可达状态常用正无穷，求最大值的不可达状态常用负无穷；使用哨兵值时要保证它不与真实答案混淆，并避免在不可达状态上直接加减导致溢出。

有帮助，赞一个

去预览

0/2000

这里空空如也