专栏文章

【动态规划】常见基础DP优化技巧

LLittle_Cake_qwq
算法·理论参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mlia780n
此快照首次捕获于
2026/02/12 01:06
上周
此快照最后确认于
2026/02/19 01:15
17 小时前
查看原文

前言

这是我的第一篇文章，有建议的可以私信我或评论 QwQ。
update：2026.1.31 感谢 @Jacken 指出错误。

正文

废话不多说直接开讲

1. 前缀和优化

前缀和优化 DP 常出现在计数 DP 中，此时的状态通过一段区间和来转移。

例题：AtCoder-dp_m Candies

这个题真的是典中典了。
设状态 dpi,jdp_{i,j} 表示前 ii 个小朋友分到 jj 颗糖果，明显的，有转移： dpi,j=∑k=max⁡(0,j−ai)jdpi−1,kdp_{i,j}=\sum_{k=\max(0,j-a_i)}^jdp_{i-1,k} 时间复杂度是 O(n×k2)O(n\times k^2)，需要优化。
不难发现状态转移是个区间和，所以设 si,j=∑k=0jdpi,ks_{i,j}=\sum_{k=0}^jdp_{i,k}，则转移就变成了 O(1)O(1) 的： dpi,j=si−1,j−si−1,j−ai−1dp_{i,j}=s_{i-1,j}-s_{i-1,j-a_i-1} 时间复杂度为 O(n×k)O(n\times k)，可以通过本题。
代码
CPP
int main()
{
	n=read(),m=read();
    for(int i=0;i<=m;i++) s[i]=1; //滚掉一维
    for(int i=1;i<=n;i++)
	{
    	int a;a=read();
    	for(int j=0;j<=m;j++)
		{
    		if(j<=a) dp[i][j]=(dp[i][j]+s[j])%mod;
			else dp[i][j]=(dp[i][j]+s[j]-s[j-a-1])%mod;	
		}
		s[0]=dp[i][0];
		for(int j=1;j<=m;j++) s[j]=s[j-1]+dp[i][j];
	}
	cout<<dp[n][m];
	return 0;
}

2. mx/mn 数组优化

这种优化方法一般出现在求最优解 DP 中。

例题：P1107 雷涛的小猫

也是一个经典题目了。
设状态 dpi,jdp_{i,j} 表示小猫在第 jj 颗柿子树的高度 ii 能吃到的最大柿子数，ai,ja_{i,j} 表示这个位置有没有柿子。
在位置 (i,j)(i,j) 时，小猫既可以从上面一层过来，也可以从其他树跳过来，所以有转移： dpi,j=max⁡k=1nmax⁡(dpi+1,j,dpi+d,k)+ai,jdp_{i,j}=\max_{k=1}^n\max(dp_{i+1,j},dp_{i+d,k})+a_{i,j} 时间复杂度 O(n2×h)O(n^2\times h)，考虑优化。
不难发现柿子式子等价于： dpi,j=max⁡(dpi+1,j,max⁡k=1ndpi+d,k)+ai,jdp_{i,j}=\max(dp_{i+1,j},\max_{k=1}^ndp_{i+d,k})+a_{i,j} 其中的 max⁡k=1ndpi+d,k\max_{k=1}^ndp_{i+d,k} 会被反复利用，所以设 mxi=max⁡k=1ndpi,kmx_i=\max_{k=1}^ndp_{i,k}，式子变为： dpi,j=max⁡(dpi+1,j,mxi+d)+ai,jdp_{i,j}=\max(dp_{i+1,j},mx_{i+d})+a_{i,j} 时间复杂度 O(n×h)O(n\times h)，可以通过本题。
代码
CPP
int main(){
	n=read(),h=read(),d=read();
	for(int i=1;i<=n;i++)
	{
		int t,x;t=read();
		while(t--) x=read(),a[x][i]++;
	}
	for(int i=h;i>=0;i--)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(dp[i+1][j],mx[i+t])+a[i][j];
			mx[i]=max(mx[i],dp[i][j]);
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans;
	return 0;
}

3. 单调队列（单调栈）优化

重头戏来了！
不会模板的可以去 P1886【模板】单调队列 / 滑动窗口 和 P5788 【模板】单调栈 学习。
这种一般出现在通过区间最大值转移的 DP 优化中。

例题：P1725 琪露诺

设 dpidp_i 为到达位置 ii 的最大值，明显地有转移： dpi=max⁡j=max⁡(0,i−r)i−ldpj+aidp_i=\max_{j=\max(0,i-r)}^{i-l}dp_j+a_i 时间复杂度 O(n2)O(n^2)，需要优化。
不难发现 max⁡j=max⁡(0,i−r)i−ldpj\max_{j=\max(0,i-r)}^{i-l}dp_j 相当于滑动窗口，所以可以拿单调队列来优化，时间复杂度 O(n)O(n)，可以通过此题。
代码
CPP
int main()
{
	n=read(),l=read(),r=read();
	for(int i=0;i<=n;i++) a[i]=read(),dp[i]=-INF;
	dp[0]=0;
	for(int i=l;i<=n;i++)
	{
		while(!q.empty()&&dp[q.back()]<dp[i-l]) q.pop_back();
		q.push_back(i-l);
		while(!q.empty()&&q.front()<i-r) q.pop_front();
		dp[i]=dp[q.front()]+a[i];
	}
	int ans=-INF;
	for(int i=n-r+1;i<=n;i++) ans=max(ans,dp[i]);//注意答案
	cout<<ans;
	return 0;
}

4. 贪心（数学）优化

这类优化一般在求最优解 DP 中出现，我感觉这类优化挺神奇的。

例题：P13957 [ICPC 2023 Nanjing R] 背包

设 dpi,j,ldp_{i,j,l} 表示买到第 ii 颗宝石，获得了 ll 颗免费的宝石，花了 jj 的钱的最大美丽度。要么免费拿，要么买，要么不买，所以有转移： dpi,j,l=max⁡(dpi−1,j,l,dpi−1,j−wi,l+vi,dpi−1,j,l−1+vi)dp_{i,j,l}=\max(dp_{i-1,j,l},dp_{i-1,j-w_i,l}+v_i,dp_{i-1,j,l-1}+v_i) 时间复杂度 O(n×W×k)O(n\times W\times k)，需要优化。
通过贪心，不难（其实很难）发现选取 kk 个价格最大的宝石是最优的，所以说我们只需要按 wiw_i 升序排序，设 dpi,jdp_{i,j} 表示前 ii 个宝石花 jj 的钱的最大美丽度，然后免费的就选后 n−in-i 个中美丽度最大的就好了。
时间复杂度 O(n×W+n2×log⁡n)O(n\times W+n^2\times \log n)，可以通过本题。
代码
CPP
int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++) a[i].w=read(),a[i].v=read;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) 
	{
		for(int j=m;j>=a[i].v;j--) 
			dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
		priority_queue<int> q;
		for(int j=i+1;j<=n;j++) q.push(a[j].v);
		int qwq=dp[m];
		for(int j=1;j<=k;j++)	
			if(!q.empty()) qwq+=q.top(),q.pop();
		ans=max(ans,qwq);
	}
	cout<<ans; 
	return 0;
}

最后

你可以拿一些题练手咯：

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...