DP 复习笔记：状态可达、区间选择与双向 LIS

今天的 6 道 DP 题可以整理成四类：

1. 可达状态 DP：变数；
2. 前缀最优 DP：扑克游戏；
3. 二分优化 LIS：最长上升子序列 2；
4. 双向 LIS：登山、怪盗基德的滑翔翼、合唱队形。

做 DP 时先写清楚一句话：dp 到底表示什么。状态含义不同，初始化、转移和答案也会不同。

---

一、可达状态 DP

1. 什么时候使用

题目经过若干次操作，每次有几种选择，最后询问有多少种不同结果。这类题可以用 dp[i][j] 记录经过 i 次操作后，数值 j 能不能出现。

2. 变数

每次可以：

• 把偶数除以 $2$；
• 把当前数字减去 $1$；
• 数字变成 $0$ 后，后面的操作仍保持为 $0$。

定义：

dp[i][j]：使用 i 次魔法以后，能否得到 j

初始只有原数 s 可以出现：

dp[0][s]=1

反过来考虑 j 是从哪里来的：

• 上一步是 j+1，减去 $1$ 后得到 j；
• 上一步是 2*j，除以 $2$ 后得到 j。

所以：

dp[i][j] = dp[i-1][j+1] 或 dp[i-1][2*j]

只依赖上一层，可以使用滚动数组节省空间。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010;
int s,n,ans;
bool dp[2][N];
signed main(){
	cin>>s>>n;
	dp[0][s]=1;
	for(int i=1;i<=n;i++){
		int now=i%2,last=(i-1)%2;
		for(int j=0;j<=s;j++) dp[now][j]=0;
		for(int j=0;j<=s;j++){
			//上一步从j+1执行减1，可以到达j
			if(j+1<=s&&dp[last][j+1]) dp[now][j]=1;
			//上一步从2*j执行除2，可以到达j
			if(j*2<=s&&dp[last][j*2]) dp[now][j]=1;
		}
	}
	for(int j=0;j<=s;j++) ans+=dp[n%2][j];
	cout<<ans<<"\n";
	return 0;
}

易错点

• dp 记录的是“能否到达”，不是到达次数，所以使用 bool。
• 最后统计的是可达位置的数量，不是把所有操作方案相加。
• j=0 仍可由 0/2 得到 0，因此数字到达 $0$ 后会一直保留。

---

二、前缀最优 DP

1. 扑克游戏

如果第 j 张牌和第 i 张牌花色相同，就可以取走从 j 到 i 的所有牌。每张牌只能取一次，要求最大总分。

定义：

dp[i]：只考虑前 i 张牌时，可以得到的最大分数

计算 dp[i] 时有两种选择。

不取第 i 张牌

dp[i]=dp[i-1]

取以第 i 张牌结尾的一段

枚举前面的 j。当 color[j]==color[i] 时，可以取走 [j,i]：

dp[i]=max(dp[i],dp[j-1]+区间[j,i]的点数和)

使用前缀和：

区间[j,i]的和 = sum[i]-sum[j-1]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010;
int n,color[N],sum[N],dp[N],x;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>color[i];
	for(int i=1;i<=n;i++){
		cin>>x;
		sum[i]=sum[i-1]+x;
	}
	for(int i=1;i<=n;i++){
		dp[i]=dp[i-1];//不选择以i结尾的区间
		for(int j=1;j<i;j++){
			if(color[j]==color[i]){
				//选择区间[j,i]，前面只能接dp[j-1]
				dp[i]=max(dp[i],dp[j-1]+sum[i]-sum[j-1]);
			}
		}
	}
	cout<<dp[n]<<"\n";
	return 0;
}

易错点

• [j,i] 包含第 j 张牌，区间和必须写成 sum[i]-sum[j-1]。
• 如果写成 sum[i]-sum[j]，第 j 张牌的点数会被漏掉。
• 选择 [j,i] 后，前面的最优结果只能接 dp[j-1]，这样区间才不会重叠。
• 必须先写 dp[i]=dp[i-1]，表示可以不取第 i 张牌。

---

三、二分优化最长上升子序列

1. 为什么普通 LIS 不够快

普通 LIS 用两层循环，复杂度是 $O(n^2)$。当 $n$ 达到 $10^6$ 时无法通过，需要用二分优化到 $O(n\log n)$。

2. dp 数组的新含义

这里的 dp[i] 不再表示以某个位置结尾的答案，而表示：

dp[len]：长度为 len 的严格上升子序列中，最小的结尾数字

结尾越小，后面越容易接入新的数字，所以要尽量让每个 dp[len] 小。

dp[1..cnt] 始终严格递增，可以二分查找。

3. 每个数字如何处理

读到数字 x 时：

• 如果 x>dp[cnt]，它可以接在当前最长序列后面，长度加一；
• 否则找到第一个 >=x 的位置，用 x 替换它。

替换不会让当前答案变短，只是让这个长度的结尾更小。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000+10;
int n,dp[N],cnt,x;
//查找dp中第一个大于等于x的位置
int bs(int x){
	int l=1,r=cnt,ans=cnt+1;
	while(l<=r){
		int mid=(l+r)/2;
		if(dp[mid]>=x){
			ans=mid;
			r=mid-1;
		}else l=mid+1;
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		int p=bs(x);
		dp[p]=x;
		if(p>cnt) cnt=p;
	}
	cout<<cnt<<"\n";
	return 0;
}

4. 二分细节

• 找到答案后保存的是位置 mid，不是 mid-1，也不是数字 x。
• 缩小右边界要写 r=mid-1，不能只写 r--。
• 最终答案是长度 cnt，不是 dp[cnt]。dp[cnt] 是结尾数字。
• 严格上升要找第一个 >=x 的位置。如果题目要求不下降，则要找第一个 >x 的位置。
• 写成上面的统一二分后，即使第一个数字是 $0$ 也能正确处理。

---

四、双向 LIS

很多题目不是一直上升，而是需要从左右两个方向分别计算。

1. 先升后降的最长序列

以第 i 个数作为最高点：

f[i]：从左边选到i，并以a[i]结尾的最长严格上升子序列
g[i]：从i开始向右选的最长严格下降子序列

左边从小到大计算：

for(int i=1;i<=n;i++){
	f[i]=1;
	for(int j=1;j<i;j++){
		if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
	}
}

右边从大到小计算：

for(int i=n;i>=1;i--){
	g[i]=1;
	for(int j=n;j>i;j--){
		if(a[j]<a[i]) g[i]=max(g[i],g[j]+1);
	}
}

两边合并时，最高点 a[i] 被计算了两次，所以要减一：

以i为最高点的最长长度 = f[i]+g[i]-1

2. 登山

登山要求最多浏览多少个景点，答案直接是最长先升后降序列的长度：

ans=max(ans,f[i]+g[i]-1);

3. 合唱队形

合唱队形与登山的状态完全相同，但题目问的是最少让多少人出列。

最少出列人数 = n-最长合唱队形人数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int n,a[N],f[N],g[N],best;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++){
			if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
		}
	}
	for(int i=n;i>=1;i--){
		g[i]=1;
		for(int j=n;j>i;j--){
			if(a[j]<a[i]) g[i]=max(g[i],g[j]+1);
		}
	}
	for(int i=1;i<=n;i++){
		//最高点i在f和g中各计算一次，所以减1
		best=max(best,f[i]+g[i]-1);
	}
	cout<<n-best<<"\n";
	return 0;
}

4. 登山和合唱队形对比

题目	状态	合并	输出
登山	左侧上升 f，右侧下降 g	f[i]+g[i]-1	最大保留人数 best
合唱队形			最少出列人数 n-best

今天“合唱队形”中双向状态已经正确，错误在最后输出了 best。题目要求的是出列人数，应输出 n-best。

---

五、只能选择一个方向的问题

怪盗基德的滑翔翼

怪盗可以从任意建筑出发，选择向左或向右，但中途不能改变方向，并且高度必须不断下降。

分别计算：

• 向一个方向能够经过的最长下降子序列；
• 向另一个方向能够经过的最长下降子序列。

最终只能二选一：

ans=max(ans,max(f[i],g[i]))

不能写成 f[i]+g[i]-1，因为相加表示从一个方向到达起点后又转向另一个方向，违反“不能改变方向”。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
int t,n,a[N],f[N],g[N],ans;
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		ans=0;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++){
			f[i]=1;
			for(int j=1;j<i;j++){
				if(a[j]>a[i]) f[i]=max(f[i],f[j]+1);
			}
		}
		for(int i=n;i>=1;i--){
			g[i]=1;
			for(int j=n;j>i;j--){
				if(a[j]>a[i]) g[i]=max(g[i],g[j]+1);
			}
		}
		for(int i=1;i<=n;i++) ans=max(ans,max(f[i],g[i]));
		cout<<ans<<"\n";
	}
	return 0;
}

---

六、双向 DP 的判断方法

先看题目是否允许改变方向：

• 先上升再下降：左右状态需要合并，使用 f[i]+g[i]-1。
• 只能向左或向右走：左右状态只能取最大值，使用 max(f[i],g[i])。

再看题目问什么：

• 问最多保留、浏览或经过多少个：输出最长长度；
• 问最少删除或出列多少个：输出 n-最长长度。

---

七、本次提交前检查清单

1. dp 表示可达、最大分数、最长长度，还是最小结尾？
2. 前缀和求 [l,r] 是否写成 sum[r]-sum[l-1]？
3. 二分保存的是位置还是数值？
4. LIS 最终输出的是 cnt，不是 dp[cnt]？
5. 严格上升和下降是否使用严格不等号？
6. 双向状态应该相加，还是只能二选一？
7. 最高点合并时是否减去重复的一次？
8. 题目要求最长保留人数，还是最少删除人数？
9. 多组数据中 ans、f、g 是否重新初始化？

最后记住三句话：

前缀 DP 先考虑“不选当前项”。

二分 LIS 维护的是每种长度的最小结尾，答案是长度 cnt。

双向 LIS 先判断能否改变方向，再决定相加还是取最大值。