动态规划算法

小码农<^_^>

1452人浏览 · 2025-04-12 16:27:55

小码农<^_^> · 2025-04-12 16:27:55 发布

动态规划可以说是整个算法基础篇中，最难的⼀章：
• ⾸先，⼊⻔难。刚开始接触动态规划，你会觉得这玩意有点晦涩 + ⽞学，稀⾥糊涂的就把问题解决
了。不⽤担⼼，等做过五六道题⽬之后，就能理解动态规划是如何解决问题的；— 坚持学、重复学
• 其次，题型多。不仅算法基础篇会讲到动态规划，在算法提⾼篇还会再讲。动态规划细分的话，可
以分出⼗⼏种类型。所以，学习的成本是⽐较⾼的；
• 最后，题⽬难。在竞赛中，如果遇到动态规划的问题，只要不是经典题型，那么⼤概率就是以压轴
题的形式出现。
但是，即使很难，我们也要慢慢去学习。想取得好成绩，动态规划是避不开的。不过⼤家放⼼，往后
讲解的时候，我会循序渐进的进⾏，相信⼤家都是可以听得懂的。

在这里插入图片描述

1、什么是动态规划？

在这里插入图片描述

2、入门

2.1 下楼梯

https://www.luogu.com.cn/record/208148293
在这里插入图片描述

代码

#include <iostream>
using namespace std;

int n;
const int N=100;
long long f[N];

long long func(int n)
{
	f[1]=1,f[2]=2,f[3]=4;
	for(int i=4;i<=n;i++)
	{
		f[i]=f[i-1]+f[i-2]+f[i-3];
	}
	return f[n];
}

int main() 
{
	cin>>n;
	cout<<func(n);
	return 0;
}

2.2 数字三角形

https://www.luogu.com.cn/record/208159091

code

#include<iostream>
using namespace std;

int r;
const int N=1e3+10;
int f[N][N];

int main()
{
	cin>>r;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
			cin>>f[i][j];
	
	for(int i=1;i<=r;i++)
		for(int j=1;j<=i;j++)
			f[i][j]+=max(f[i-1][j],f[i-1][j-1]);
	
	int ret=0;
	
	for(int i=1;i<=r;i++)
		ret=max(ret,f[r][i]);
	
	cout<<ret;
	return 0;
 }

3、基础线性dp

线性dp 是动态规划问题中最基础、最常⻅的⼀类问题。它的特点是状态转移只依赖于前⼀个或前⼏个
状态，状态之间的关系是线性的，通常可以⽤⼀维或者⼆维数组来存储状态。
我们在⼊⻔阶段解决的《下楼梯》以及《数字三⻆形》其实都是线性 dp，⼀个是⼀维的，另⼀个是⼆
维的。

3.1 台阶问题

https://www.luogu.com.cn/problem/P1192

在这里插入图片描述

code

在这里插入图片描述

3.2 最大字段和

https://www.luogu.com.cn/problem/P1115
在这里插入图片描述

code

#include<iostream> 
using namespace std;

const int N=2e5+10;
int a[N],p[N];
int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		p[i]=max(a[i],p[i-1]+a[i]);
	}
	
	int ret=-1e10;
	for(int i=1;i<=n;i++)
	{
		ret=max(ret,p[i]);
	}
	
	cout<<ret;
	return 0;
}

3.3 传球游戏

https://www.luogu.com.cn/record/208346921
在这里插入图片描述

代码

#include <iostream>
using namespace std; 

int a[35][35];
int n,m;

int main() 
{
	cin>>n>>m;
	a[0][1]=1;
	
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(j==1) a[i][j]=a[i-1][2]+a[i-1][n];
			else if(j==n) a[i][j]=a[i-1][1]+a[i-1][n-1];
			else a[i][j]=a[i-1][j-1]+a[i-1][j+1];
		}
	}
	
	cout<<a[m][1];
	return 0;
}

4、路径类dp

路径类 dp 是线性 dp 的⼀种，它是在⼀个 n × m 的矩阵中设置⼀个⾏⾛规则，研究从起点⾛到终点的
⽅案数、最⼩路径和或者最⼤路径和等等的问题。
⼊⻔阶段的《数字三⻆形》其实就是路径类 dp。

4.1 矩阵的最小路径和

https://www.nowcoder.com/practice/38ae72379d42471db1c537914b06d48e?tpId=230&tqId=39755&ru=/exam/oj

code

#include<iostream>
#include<cstring>
using namespace std;

const int N=510;
int d[N][N];
int n,m;

int main()
{
	cin>>n>>m;
	
	memset(d,0x3f,sizeof d);
	
	d[0][1]=0;
		
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int x; cin>>x;
			d[i][j]=min(d[i-1][j],d[i][j-1])+x;
		}
	}
	
	cout<<d[n][m];
	return 0;
 }

4.2 迷雾森林

https://ac.nowcoder.com/acm/problem/53675

code

#include<iostream>
using namespace std;

const int N=3010,MOD=2333;
int a[N][N],d[N][N];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	
	d[n][0]=1;
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==0) d[i][j]=(d[i+1][j]+d[i][j-1])%MOD;
		}
	}
	
	cout<<d[1][m];
	return 0;
 }

4.3 过河卒

https://www.luogu.com.cn/problem/P1002

code

#include<iostream>
#include<cmath>
using namespace std;

const int N=30;
long long f[N][N];
int n,m,x,y;

bool check(int i, int j)
{
	return (i == x && j == y) || (i != x && j != y && abs(i - x) + abs(j - y)
	== 3);
}

int main()
{
	cin>>n>>m>>x>>y;
	n++,m++,x++,y++;
	
	f[0][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(check(i,j)) continue;
			else f[i][j]=f[i-1][j]+f[i][j-1];
		}
	
	cout<<f[n][m]<<endl;
	return 0;
}

5 经典线性dp

经典线性 dp 问题有两个：最⻓上升⼦序列（简称：LIS）以及最⻓公共⼦序列（简称：LCS），这两道
题⽬的很多⽅⾯都是可以作为经验，运⽤到别的题⽬中。⽐如：解题思路，定义状态表⽰的⽅式，推
到状态转移⽅程的技巧等等。
因此，这两道经典问题是⼀定需要掌握的。

5.1 最长上升子序列（1）

https://www.luogu.com.cn/problem/B3637
在这里插入图片描述

code

#include<iostream>
using namespace std;

const int N=5010;
int a[N],f[N];
int n;

int 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=i-1;j>=1&&i-j>=0;j--)
		{
			if(a[j]<a[i])	
				f[i]=max(f[j]+1,f[i]);
		}
	}
	
	int ret=0;
	for(int i=1;i<=n;i++)
		ret=max(ret,f[i]);
		
	cout<<ret;
	return 0;
}

5.2 最长上升子序列（2）

https://ac.nowcoder.com/acm/problem/226831
在这里插入图片描述

code

#include<iostream>
using namespace std;

const int N=1e6+10;
int a[N],f[N];
int n;

int main()
{
    cin>>n;
    int len=0;
    
    for(int i=1;i<=n;i++) cin>>a[i];
    
    for(int i=1;i<=n;i++) 
    {
        if(len==0||f[len]<a[i]) f[++len]=a[i];
        else
        {
            int l=1,r=len;
            while(l<r)
            {
                int mid=(l+r)/2;
                if(f[mid]>=a[i]) r=mid;
                else l=mid+1;
            }
            f[l]=a[i];
        }
    }
    
    cout<<len<<endl;
    return 0;
}

5.3 牛可乐和最长公共子序列

https://ac.nowcoder.com/acm/problem/235624

在这里插入图片描述

code

#include<iostream>
using namespace std;

string s,t;
int f[5010][5010];

int main()
{
	while(cin>>s>>t)
	{
		int n=s.size(),m=t.size();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(s[i-1]==t[j-1]) f[i][j]=f[i-1][j-1]+1;
				else f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
		}
		cout<<f[n][m]<<endl;
	}

	return 0;
}

5.4 合唱队形

https://www.luogu.com.cn/problem/P1091

code

#include<iostream>
using namespace std;

const int N=110;
int a[N],l[N],r[N];
int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	//从左向右找最大上升子序列
	for(int i=1;i<=n;i++)
	{
		l[i]=1;
		for(int j=1;j<i;j++)
		{
			if(a[j]<a[i])
				l[i]=max(l[i],l[j]+1);
		}
	}
	
	//从右向左找最大上升子序列
	for(int i=n;i>=1;i--)
	{
		r[i]=1;
		for(int j=n;j>i;j--)
		{
			if(a[j]<a[i])
				r[i]=max(r[i],r[j]+1);
		}
	}
	
	//找到两者相加最大得值 
	int ret=0;
	for(int i=1;i<=n;i++) ret=max(ret,l[i]+r[i]-1);
	
	cout<<n-ret<<endl;
	return 0;
}

5.5 编辑距离

https://www.luogu.com.cn/problem/P2758
在这里插入图片描述

code

#include<iostream>
using namespace std; 

const int N=2020;
int f[N][N];
string s1,s2;

int main()
{
	cin>>s1>>s2;
	int n=s1.size(),m=s2.size();
	s1=" "+s1,s2=" "+s2; 
	//初始化
	for(int i=0;i<=n;i++) f[i][0]=i;
	for(int i=0;i<=m;i++) f[0][i]=i;
	
	//填表
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(s1[i]==s2[j]) f[i][j]=f[i-1][j-1];
			else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
		}
	 
	cout<<f[n][m]<<endl;
	return 0;
}

6 背包问题

6.1 01背包问题

背包问题是动态规划中最经典的问题，很多题⽬或多或少都有背包问题的影⼦。它的基本形式是：给
定⼀组物品，每个物品有体积和价值，在不超过背包容量的情况下，选择物品使得总价值最⼤。
背包问题有多种变体，主要包括：

01 背包问题：每种物品只能选或不选（选 0 次或 1 次）。
完全背包问题：每种物品可以选择⽆限次。
多重背包问题：每种物品有数量限制。
分组背包问题：物品被分为若⼲组，每组只能选⼀个物品。
混合背包：以上四种背包问题混在⼀起。
多维费⽤的背包问题：限定条件不⽌有体积，还会有其他因素（⽐如重量）。
除了经典的总价值最⼤问题，还会有：
⽅案总数。
最优⽅案。
⽅案可⾏性。
输出具体⽅案。
因此，背包问题种类⾮常繁多，题型⾮常丰富。但是，尽管背包有很多变形，都是从 01 背包问题演化
过来的。所以，⼀定要把 01 背包问题学好。

6.1.1 模版

请添加图片描述

code

6.2 完全背包

6.1.1 （模版）完全背包

https://ac.nowcoder.com/acm/problem/226516

code

8 区间dp

区间 dp 也是线性 dp 的⼀种，它⽤区间的左右端点来描述状态，通过⼩区间的解来推导出⼤区间的
解。因此，区间 DP 的核⼼思想是将⼤区间划分为⼩区间，它的状态转移⽅程通常依赖于区间的划分
点。
常⽤的划分点的⽅式有两个：
• 基于区间的左右端点，分情况讨论；
• 基于区间上某⼀点，划分成左右区间讨论。

8.1 回文子串

https://www.luogu.com.cn/problem/P1435
在这里插入图片描述

code

#include<iostream>
using namespace std;

const int N=1010;
int f[N][N];

int main()
{
	string s; cin>>s;
	int n=s.size();
	s=" "+s;
	
	for(int len=1;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			if(s[i]==s[j]) f[i][j]=f[i+1][j-1];
			else f[i][j]=min(f[i+1][j],f[i][j-1])+1;
		}
	}
	
	cout<<f[1][n]<<endl;
	return 0;
}

8.2 Treats for the Cows G/S

https://www.luogu.com.cn/problem/P2858
在这里插入图片描述

code

在这里插入图片描述

8.3 石子合并（弱化版）

https://www.luogu.com.cn/problem/P1775
在这里插入图片描述

code

#include<iostream>
#include<cstring>
using namespace std;

const int N=310;
int a[N],sum[N];
int f[N][N];
int n;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	
	memset(f,0x3f,sizeof f);
	for(int i=0;i<=n;i++) f[i][i]=0; 
	
	for(int len=1;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			int t=sum[j]-sum[i-1];
			for(int k=i;k<j;k++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+t);
			}
		}
	}
	
	cout<<f[1][n]<<endl;
	return 0;
}

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

天工造物局

所有评论(0)

查看更多评论

小码农<^_^>

@2401_87257864

已为社区贡献4条内容

动态规划算法

小码农<^_^>

动态规划算法

1、什么是动态规划？

2、入门

2.1 下楼梯

代码

2.2 数字三角形

code

3、基础线性dp

3.1 台阶问题

code

3.2 最大字段和

code

3.3 传球游戏

代码

4、路径类dp

4.1 矩阵的最小路径和

code

4.2 迷雾森林

code

4.3 过河卒

code

5 经典线性dp

5.1 最长上升子序列（1）

code

5.2 最长上升子序列（2）

code

5.3 牛可乐和最长公共子序列

code

5.4 合唱队形

code

5.5 编辑距离

code

6 背包问题

6.1 01背包问题

6.1.1 模版

code

6.2 完全背包

6.1.1 （模版）完全背包

code

8 区间dp

8.1 回文子串

code

8.2 Treats for the Cows G/S

code

8.3 石子合并（弱化版）

code

所有评论(0)

温馨提示：您尚未绑定手机号

小码农<^_^>