动态规划讲解（炒鸡详细）--未完工
2026-05-03 18:05:26
发布于：河北
本篇文章只基于我这个学dp不到半年的萌新的一些看法
※ 本篇讲解的是递推解决dp问题的方式，有些的不好的直接喷 ※
相信大家对递推不陌生，不在此介绍（对递推陌生的先了解去）
那我就直接开始分享了？
1 什么是动态规划（Dynamic Programming, 简称DP）
1.1 个人看法
个人认为，动态规划就是：把一个复杂的大问题，拆成很多简单的小问题
有两个关键操作：
- 先把小问题的答案算出来并记录
- 后面需要这个答案的时候，直接使用
就像你做数学题，第二小问的答案中的一部分可能是由第一小问的答案推导来的
1.2 标准定义
动态规划，是一种拆分复杂问题、记忆化存储子问题解的算法思想。
适用于满足最优子结构和无后效性的问题
1.2.1 动态规划的特点
- 最优子结构：大问题的最优解，可以由若干个子问题的最优解推导得到；
- 无后效性：当前阶段的结果，只和前面已经算完的阶段有关，和未来还没做的选择没有任何关系；
- 核心思想：分治拆分 + 记忆化复用，避免暴力枚举带来的大量重复计算，提升时间效率。
2 动态规划求解步骤
个人认为，可以通过以下 步解决
2.1 状态定义（设计状态）
在第一步中，我们会定义一个数组（通常为f或dp）
我们要设置dp[i]/dp[i][j]/dp[i][j][k]当做状态，也就是说我们要清楚dp数组中当前这一项代表什么，只有清楚它的定义，我们才能进行求解状态转移方程
那么如何设计状态呢？
2.1.1 先考虑这道题需要你求什么答案？
如 爬楼梯 这道经典例题
题目要求找到爬到第 阶的方案数，故设计dp[i]为爬到第 阶的方案数
2.1.2 设计状态的核心原则
- 能代表一个完整小问题
- 能从小的推大的
- 不多余
- 满足无后效性（就是说这一项不管以后怎么选）
2.1.3 常用状态设计方案（ 或 表示？）
2.1.3.1 一维dp
- 表示前 项的最优答案
- 表示到位置 时的最值/方案数
2.1.3.2 二维dp
- 表示区间 之间的最优解
- 表示选前 个物品，容量为 时的最大价值（背包问题！）
- 表示处理到第 个或第 个之前，限制为 时的答案
- 到达位置 时的答案
2.1.4 提示：
对于高阶dp来说，dp开三维数组甚至四维数组都是常见的，下文我会讲解动态规划的优化
2.2 设置初始值（确定初始边界）
2.2.1 理解
一般来说，问题最小，最开头，不用计算就知道答案的位置需要初始化
位置如： / / / 这些开头位置 或者 全局初始化
初始化值如：
额外提一嘴，如果你想要全局初始化，可以使用如下函数：
// 设置为0
memset(数组名,0,sizeof(数组名));
// 设置为极大数
memset(数组名,0x3f,sizeof(数组名));
// 设置为极小数
memset(数组名,-0x3f,sizeof(数组名));
// 设置为任何数
fill(起始地址,结束地址,数字)
2.2.2 举例
还是以 爬楼梯 这道题为例
从第 项以后的内容都可以由前面推导而来，因此设置：
dp[0] = 1;// 到第0级只有一种方案：0
dp[1] = 1;// 到第1级只有一种方案：0->1
dp[2] = 2;// 到第2级只有两种方案：0->1->2或者0->2
2.3 推导状态转移方程
2.3.1 先理解什么是状态转移方程
状态转移方程就是：现在这个 dp 值，是从前面哪几个旧 dp 值，通过加、减、取最大、取最小、求和、求积变过来的式子。推导状态转移方程就是：看当前情况有几种选择，每种选择对应前面哪个状态，再把式子写出来。
2.3.2 通用步骤
2.3.2.1 分析当前这一步有几种可能，把所有可能的方法列出来
比如：
- 选/不选这个物品
- 从某个方向走过来
- 从前面的某一项走过来
- 区间分成左边/右边一段
对于 爬楼梯 这道题，每一级都可能从前面的 项过来
2.3.2.2 每种选择，找前面可能过来的状态
比如： 爬楼梯 这道题
连跳 步，从 来
连跳 步，从 来
连跳 步，从 来
2.3.2.3 根据题目要求，选运算规则
看题目问什么，套对应运算：
- 求总方案数、总走法、总数量 把几种情况相加
- 求最大值、最大价值 几种情况取max
- 求最小值、最少花费 几种情况取min
- 拼接区间答案 左右区间值相加 / 合并
依旧对于 爬楼梯 这道题，要求总走法，所以相加即可
2.4 取最终答案
还记得第2.1部分讲解的设计状态吗？
我们要找到能代表整道题答案的那一项：
可能存在：
最终输出答案即可
中场休息
就在刚刚，我们了解了什么是dp，以及做dp题的步骤
有没有感觉明了一些了？
大家想练题，可以去ACGO的学习部分找到相应题目
也可以去题库中找到相应题目练练手
给大家推荐一下练题内容：
| 学习内容 | 学习阶段 |
|---|---|
| 简单线性动态规划 | GESP6级 |
| 简单背包动态规划 | |
| 计数动态规划 | |
| 简单多维动态规划 | |
| 区间动态规划 | GESP7级、CSP-J常考 |
| 复杂多维动态规划 | |
| 状态压缩动态规划 | |
| 复杂线性动态规划 | |
| 复杂背包动态规划 | |
| 简单树形动态规划 | |
| 简单动态规划的优化（如单调队列、滚动数组） | |
| 复杂树形动态规划 | GESP8级、CSP-S常考、甚至NOIP |
| 数位动态规划 | |
| 复杂状态压缩动态规划 | |
| 概率动态规划 | |
| 期望动态规划 | |
| 复杂动态规划的优化（如斜率优化动态规划） |
有帮助，赞一个