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