动态规划算法详解
2025-05-20 15:39:28
发布于：重庆
前言
此篇文章在洛谷没有通过全站推荐，令人汗颜。
叠个甲先：
本文章记录的动态规划板块可能不完全，并且作者的水平并不高，有一些错误可以在回复中指出，请不要有过激言论，谢谢！o(￣▽￣)ブ
此外，如果有不理解或有文章漏掉的部分，也可以在回复板块进行指出哟！/_ \
接着进入主题，动态规划（Dynamic Programming，简称DP）是解决多阶段决策过程最优化问题的一种数学方法。它将复杂问题分解为相对简单的子问题，通过存储并重用子问题的解来避免重复计算，从而显著提高算法效率，在竞赛中显得尤为常见，以下是一些动态规划主要分支讲解。
章节1-背包DP
一、何为背包DP?
背包问题是动态规划中最经典的问题类型之一，其核心思想是在有限的容量限制下，选择物品以获得最大价值。
基本要素：
- 限制条件：总重量、总体积的限制。
- 物品集合：每个物品有重量/体积和价值。
- 选择规则：物品能否分割、重复选择等。
二、基础背包问题
1. 01背包问题
特点：每种物品最多选一次
状态定义：
dp[i][j]表示考虑前i件物品，背包容量为j时的最大价值
状态转移方程：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
也就是可以不选当前物品或选当前物品。
空间优化：
使用一维数组并逆序更新，也称“滚动数组”：
for(int i=1;i<=n;i++)
for(int j=c;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
2. 完全背包问题
特点：每种物品可以选无限次
状态转移方程：
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
也是可以不选当前物品或选当前物品。
空间优化：
正序更新一维数组（方法同01背包）：
for(int i=1;i<=n;i++)
for(int j=w[i];j<=c;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
3. 多重背包问题
特点：每种物品有数量限制。
状态转移方程：
dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);
优化方面与01背包类似，不过多赘述。
三、背包问题的变形
恰好装满：
- 初始化时
dp[0]=0，其他为-∞
方案计数：
- 将max改为sum
二维费用：
- 增加一维状态（如重量+体积限制）
分组背包：
- 每组物品只能选一个
依赖背包：
- 物品间存在依赖关系（如主件附件）
方案记录：
- 额外数组记录选择路径
四、经典例题
问题描述：
- 总时间T（背包容量）
- M株草药，每株有采集时间w[i]和价值v[i]
- 每种草药只能采一次（0/1背包）
关键代码（滚动数组优化）：
for(int i=1;i<=m;i++)
{
int w,v;
cin >> w >> v;
for(int j=t;j>=w;j--) dp[j]=max(dp[j],dp[j-w]+v);
}
五、学习建议与误区
背包DP是动态规划的重要基础，建议通过大量练习来培养对状态设计和转移方程的敏感度。
如果你对本章节感兴趣，不妨通过练习这些题目来提升背包方面的能力：
章节2-状压DP
一、何为状压DP？
状态压缩动态规划（State Compression Dynamic Programming，简称状压DP）是动态规划的一种特殊形式，主要用于处理状态空间庞大但每个状态可以用紧凑方式表示的问题。这类问题通常涉及集合操作或排列组合，其中状态可以用二进制位来表示某些特征的存在与否。
状压DP的核心思想是：将复杂的状态信息压缩为一个简单的整数（通常是二进制数）。
比如说，现在有五个物品，用 和 代表是否选择，现在如果是以下情况：
1 1 0 0 1
那么就可以转化为 进制，压缩为 。
二、什么时候使用状压DP
状压DP通常适用解决 集合覆盖问题、棋盘覆盖问题、状态切换问题、排列组合问题
这些问题的一个共同特点是：状态可以分解为多个独立的二元选择，每个选择可以用一个二进制位表示，此时可以使用状态压缩来将该二进制数组转化为十进制。
三、状压DP的基本实现
状压DP的实现通常包含以下几个要素：
- 状态表示：用一个整数的二进制位表示各个子状态。
- 状态转移：根据当前状态和可能的操作，推导出下一状态。
- 确定范围：确定问题的起始条件和结束状态。
示例代码框架（C++）
int dp[1 << N];//状态压缩DP数组，N是状态位数
memset(dp,0x3f,sizeof(dp));//初始化为极大值
dp[初始状态]=初始状态;//设置初始状态
for(int mask=0;mask<(1<<N);mask++)
{
if(dp[mask]==INF) continue;//跳过不可达状态
for(int next=0;next<N;next++)
{
if(!(mask&(1<<next)))//检查是否可以选择next
{
int now=mask|(1<<next);//状态转移
dp[now]=min(dp[now],dp[mask]+cost[next]);
}
}
}
int ans=dp[目标状态];
四、经典问题分析
由于村庄数量n的范围是 ，我们可以使用状态压缩动态规划来解决这个问题。状态压缩DP是解决小规模 问题的有效方法。
状态设计
我们定义 表示：
-
表示已经访问过的村庄集合
-
表示当前所在的村庄编号
-
表示从起点出发，经过mask中的村庄到达i的最短路径长度
状态转移方程
dp[mask|(1<<(j-1))][j] = min(dp[mask | (1 << (j-1))][j], dp[mask][i] + dist[i][j])
核心代码
for(int mask=1;mask<(1<<n);mask++)
{
for(int i=0;i<n;i++)
{
if(!(mask&(1<<i))) continue;
for(int j=0;j<n;j++)
{
if(mask&(1<<j)) continue;
int new_mask = mask|(1<<j);
dp[new_mask][j]=min(dp[new_mask][j],dp[mask][i]+dist[i][j]);
}
}
}
六、状压DP的局限性
由于使用位掩码，通常只能处理 左右的问题。
七、尾言
如果你想练习状压DP，可以参照洛谷的状态压缩动态规划题单进行练习。
章节3-区间DP
浅谈区间动态规划（DP）
一、何为区间DP？
区间动态规划是动态规划的一个重要分支，主要用于解决涉及区间操作的最优化问题。这类问题的特点是问题的解可以通过其子区间的解组合得到，具有明显的区间划分特性。
核心特征：
问题可以分解为子区间问题，区间可以合并产生更大区间的解，比较类似分治算法。
二、区间DP的三大要素
1. 状态定义
通常表示为dp[i][j]，表示区间[i,j]上的最优解
2. 状态转移方程
一般形式：
dp[i][j]=max(dp[i][k]+dp[k+1][j]+cost(i,j,k))
其中k是区间[i,j]的分割点
3. 边界条件
- 区间长度为1时的初始值
- 通常
dp[i][i]=base_case
三、区间DP模型
1. 区间合并
特点：通过合并相邻区间获得价值
2. 区间分割
特点：通过分割区间获得最优解
3. 区间匹配类
特点：处理区间端点间的匹配关系
4. 区间覆盖类
特点：用子区间覆盖目标区间
四、经典例题
问题描述：
将N堆石子排成圆形，每次合并相邻两堆，得分是新堆的石子数，求最大/最小总得分。
关键代码：
for(int len=2;len<=n;len++)//区间长度
{
for(int i=1;i+len-1<=2*n;i++)//起点
{
int j=i+len-1;
dp_min[i][j]=INF;
dp_max[i][j]=-INF;
for(int k=i;k<j;k++)//分割点
{
dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]+sum[j]-sum[i-1]);
dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]+sum[j]-sum[i-1]);
}
}
}
五、区间DP的常见错误
（由于蒟蒻作者的区间DP错误率比较高，所以加了这一部分）
- 错误的枚举顺序
- 遗漏边界条件
- 状态转移不完整
- 预处理不足
区间DP细节繁多，一定要多加注意！
六、尾言
以下是一些进阶的区间DP内容，感兴趣的话可以看一看。
- 多维平面上的区间划分。
- 区间操作带有额外权重。
- 考虑概率因素的区间问题。
- 支持动态修改的区间问题。
- 如区间DP与数据结构结合。
区间DP是竞赛中的高频考点，建议通过大量练习培养对区间划分的敏感度。
如果想要练习，可以参照洛谷的区间与环形动态规划题单进行练习哦！
点赞记录：
有帮助，赞一个