DP 复习笔记：LIS、LCS 与计数 DP

今天的 DP 题可以归纳为三类：

1. 最长上升子序列及其变形；
2. 最长公共子序列；
3. 带间隔限制的方案计数。

一、写 DP 前先确定四件事

1. 状态：dp[i] 或 dp[i][j] 表示什么？
2. 转移：当前状态可以从哪些已经算出的状态得到？
3. 初值：只选当前元素、空序列、第一行和第一列分别是多少？
4. 答案：答案是最后一个状态，还是所有状态中的最大值？

状态的含义一旦改变，初值和转移也必须一起改变。不能只记代码。

---

二、最长上升子序列 LIS

1. 什么是子序列

子序列只要求元素在原数组中的先后顺序不变，不要求位置连续。

例如数组 1 7 3 5 9 中，1 3 5 9 是上升子序列；1 5 3 不是，因为数值没有严格上升。

2. 状态设计

dp[i] 表示：以第 i 个数结尾的最长上升子序列长度。

每个数单独都能组成长度为 $1$ 的子序列，所以：

dp[i] = 1

枚举前面的 j。如果 j<i 且 a[j]<a[i]，就可以把 a[i] 接在以 a[j] 结尾的上升子序列后面：

dp[i] = max(dp[i], dp[j] + 1)

答案是所有 dp[i] 的最大值，因为最长上升子序列不一定以最后一个数结尾。

3. LIS 模板

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int n,a[N],dp[N],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		dp[i]=1;//只选择a[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]);
	}
	cout<<ans<<"\n";
	return 0;
}

4. 易错点

• 严格上升使用 <，不能写成 <=。
• dp[i] 必须先设为 1。不要让它从 0 开始后再输出 ans+1，这样不直观，也更容易在变形题中出错。
• 判断条件比较的是数组元素 a[j] 和 a[i]，不是比较 dp[j] 和 dp[i]。
• 答案是所有 dp[i] 的最大值，不是固定输出 dp[n]。

---

三、LIS 的常见变形

1. 最大上升子序列和

这道题仍然要求严格上升，但目标从“长度最大”变成“元素总和最大”。

dp[i] 表示：以 a[i] 结尾的上升子序列的最大元素和。

只选择 a[i] 时，和就是 a[i]，所以初值为：

dp[i] = a[i]

如果 a[j]<a[i]：

dp[i] = max(dp[i], dp[j] + a[i])

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int n,a[N],dp[N],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		dp[i]=a[i];//只选择当前数字时，总和为a[i]
		for(int j=1;j<i;j++){
			if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<"\n";
	return 0;
}

注意：最长的上升子序列不一定是元素和最大的上升子序列。状态保存什么，取决于题目要求什么。

2. 最少修改次数

要让整个序列严格递增，可以先保留一个最长严格上升子序列，再修改剩余数字。

最少修改次数 = n - 最长上升子序列长度

因此先用 LIS 求出 ans，最后输出 n-ans。

当前题面第二组样例 2 2 1 输出 1，与“严格递增”定义矛盾。按照严格递增定义和题库实际通过代码，答案应为 2。复习时以严格递增和 n-LIS 为准。

3. 友好城市

每条航线有南岸坐标 x 和北岸坐标 y。两条航线不相交，意味着它们在两岸的先后顺序相同。

处理方法：

1. 先按一侧坐标 x 从小到大排序；
2. 排序后只观察另一侧坐标 y；
3. 在 y 中求最长严格上升子序列。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10010;
struct node{
	int x,y;
}a[N];
int n,dp[N],ans;
bool cmp(node x,node y){
	return x.x<y.x;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		dp[i]=1;
		for(int j=1;j<i;j++){
			if(a[j].y<a[i].y) dp[i]=max(dp[i],dp[j]+1);
		}
		ans=max(ans,dp[i]);
	}
	cout<<ans<<"\n";
	return 0;
}

易错点：

• 排序范围是 a+1 到 a+n+1，不能写成 sort(a,a+n,cmp)。
• 城市坐标存放在结构体数组 a 中，DP 长度存放在整数数组 dp 中，两者不能混在一起修改。
• 排序后求的是另一侧坐标的 LIS，不是坐标和的最大值。

---

四、最长公共子序列 LCS

1. 状态设计

给定两个序列，dp[i][j] 表示：

第一个序列的前 i 项和第二个序列的前 j 项的最长公共子序列长度。

2. 状态转移

如果当前两项相同，可以把这个相同元素接在前面的公共子序列后面：

dp[i][j] = dp[i-1][j-1] + 1

如果当前两项不同，只能选择忽略其中一项：

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3. 整数序列 LCS

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int n,a[N],b[N],dp[N][N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;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]);
		}
	}
	cout<<dp[n][n]<<"\n";
	return 0;
}

4. 字符串 LCS

C++ 字符串原本从下标 0 开始。为了继续使用从 1 开始的 DP，可以在两个字符串前各补一个无关字符。

#include<bits/stdc++.h>
using namespace std;
string a,b;
int n,m,dp[110][110];
signed main(){
	cin>>a>>b;
	n=a.size();
	m=b.size();
	a="@"+a;
	b="#"+b;
	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]);
		}
	}
	cout<<dp[n][m]<<"\n";
	return 0;
}

5. 易错点

• 两个序列长度可能不同，循环分别写到 n 和 m，不能都写到较大长度。
• 原字符串从下标 0 开始。直接从 i=1 访问会漏掉第一个字符，并可能访问越界。
• 最后应输出已经定义的 dp[n][m]，变量名不能误写成 f[n][m]。
• LCS 不要求元素连续，只要求在两个序列中的相对顺序相同。

---

五、灯会：带间隔限制的计数 DP

1. 状态设计

长度为 i 的布置中：

• dp[i][0]：第 i 个位置放彩灯的方案数；
• dp[i][1]：第 i 个位置放气球的方案数。

2. 状态转移

如果第 i 个位置放彩灯，前一个位置放什么都可以：

dp[i][0] = dp[i-1][0] + dp[i-1][1]

如果第 i 个位置放气球，前一个气球最晚只能出现在第 i-k-1 个位置。前面的 k 个位置必须全是彩灯，因此只需统计前 i-k-1 个位置的所有合法方案。

当 i-k-1<0 时，前面不能再放气球，只有“前面全是彩灯”这一种情况。

#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
const int M=5000011;
int n,k,dp[N][2];
signed main(){
	cin>>n>>k;
	dp[0][0]=1;//长度为0的空方案
	for(int i=1;i<=n;i++){
		dp[i][0]=(dp[i-1][0]+dp[i-1][1])%M;
		int p=i-k-1;
		if(p>=0) dp[i][1]=(dp[p][0]+dp[p][1])%M;
		else dp[i][1]=1;//前面全部放彩灯
	}
	cout<<(dp[n][0]+dp[n][1])%M<<"\n";
	return 0;
}

3. 易错点

• “两个气球之间至少有 k 个彩灯”对应的位置差至少为 k+1。
• 当前放气球时，应连接到长度 i-k-1 的合法方案。
• 题目要求方案数取模，每次加法后都应 %M。
• 最终答案要把结尾为彩灯和结尾为气球的方案数相加。

---

六、本次复习清单

看到题目后，先判断属于哪一种：

• 从一个序列中按顺序挑选，并要求上升：考虑 LIS。
• LIS 但目标变成总和最大：把 dp[i] 从“长度”改成“最大和”。
• 最少修改或删除多少项才能有序：考虑 n-LIS。
• 两个序列都要保持顺序，寻找共同部分：考虑 LCS。
• 要求方案数量，并限制相邻选择之间的距离：设计“当前位置选或不选”的计数 DP。

提交前重点检查：

1. dp 的初值是否符合状态含义；
2. 严格上升是否使用 <；
3. 字符串下标是否统一；
4. 两个序列的长度是否分别使用；
5. 输出变量名是否写对；
6. 方案数是否及时取模。